Файл: Учебника по курсу Основы дискретной математики и логики.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.10.2023
Просмотров: 246
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой веревкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и
Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на ребрах додекаэдра.
Слайд 99
Тема 4.1. Высказывания и операции над ними. Понятие формулы алгебры высказываний. Эквивалентные преобразования формул
Предложение, относительно которого можно вполне объективно и определенно сказать, является оно истинным или ложным, называется высказыванием. Высказывания чаще всего обозначаются большими буквами латинского алфавита, иногда с индексами. Примеры обозначений высказываний приведены в формуле (4.1).
На множестве всех высказываний задается функция истинности μ(P)
[мю от пэ], принимающая значения из множества, состоящего из двух элементов – нуль и один. Функция истинности представлена формулой (4.2).
Значение функции называют значением истинности высказывания P[пэ] или логическим значением.
Рассмотрим пример. Предложения P, Q, S[пэ кю эс] являются высказываниями. Истинными высказываниями являются высказывания P и S.
Высказывание Q[кю] – ложное высказывание. Так как про предложения R[эр] и T[тэ] нельзя сказать, будут они истинны или ложны, то R[эр] и T[тэ], вообще говоря, не являются высказываниями.
Значения функции истинности для высказываний P, Q и G[пэ кю жэ] представлены формулой (4.3).
В алгебре высказываний содержание высказываний не имеет значения, важно только, являются высказывания истинными или ложными. Поэтому
Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на ребрах додекаэдра.
Слайд 99
Тема 4.1. Высказывания и операции над ними. Понятие формулы алгебры высказываний. Эквивалентные преобразования формул
Предложение, относительно которого можно вполне объективно и определенно сказать, является оно истинным или ложным, называется высказыванием. Высказывания чаще всего обозначаются большими буквами латинского алфавита, иногда с индексами. Примеры обозначений высказываний приведены в формуле (4.1).
На множестве всех высказываний задается функция истинности μ(P)
[мю от пэ], принимающая значения из множества, состоящего из двух элементов – нуль и один. Функция истинности представлена формулой (4.2).
Значение функции называют значением истинности высказывания P[пэ] или логическим значением.
Рассмотрим пример. Предложения P, Q, S[пэ кю эс] являются высказываниями. Истинными высказываниями являются высказывания P и S.
Высказывание Q[кю] – ложное высказывание. Так как про предложения R[эр] и T[тэ] нельзя сказать, будут они истинны или ложны, то R[эр] и T[тэ], вообще говоря, не являются высказываниями.
Значения функции истинности для высказываний P, Q и G[пэ кю жэ] представлены формулой (4.3).
В алгебре высказываний содержание высказываний не имеет значения, важно только, являются высказывания истинными или ложными. Поэтому
значок μ[мю] часто опускают, каждому ложному высказыванию присваивают значение «0», каждому истинному высказыванию – значение «1».
Слайд 100
Введем операции, их еще называют логическими связками, с помощью которых можно из имеющихся высказываний создавать новые. Рассмотрим два высказывания P[пэ] и Q[кю].
Отрицанием, или инверсией, высказывания P[пэ] будем называть высказывание, которое является истинным, когда P[пэ] ложно, и является ложным, когда P[пэ] истинно. Отрицание высказывания P[пэ] читается «не
P[пэ]».
Конъюнкцией высказываний P[пэ] и Q[кю] будем называть высказывание, которое истинно тогда и только тогда, когда P[пэ] и Q[кю] истинны. Конъюнкция высказываний P[пэ] и Q[кю] читается «P[пэ] и
Q[кю]».
Дизъюнкцией высказываний P[пэ] и Q[кю] называется высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний P[пэ] и Q[кю]. Дизъюнкция высказываний P[пэ] и Q[кю] читается «P[пэ] или [кю]».
Составим таблицу истинности для операций отрицания, конъюнкции и дизъюнкции.
Конъюнкция высказываний P[пэ] и Q[кю] – это высказывание «P[пэ] и
Q[кю]», принимающее значение «1» в том случае, когда оба высказывания истинны, и значение «0» во всех остальных случаях. Конъюнкция выполняет роль связки «и».
Дизъюнкция высказываний P[пэ] и Q[кю] – это высказывание «P[пэ] или Q[кю]», принимающее значение «0» в том случае, когда оба высказывания ложны, и значение «1» во всех остальных случаях.
Дизъюнкция выполняет роль связки «или».
Слайд 100
Введем операции, их еще называют логическими связками, с помощью которых можно из имеющихся высказываний создавать новые. Рассмотрим два высказывания P[пэ] и Q[кю].
Отрицанием, или инверсией, высказывания P[пэ] будем называть высказывание, которое является истинным, когда P[пэ] ложно, и является ложным, когда P[пэ] истинно. Отрицание высказывания P[пэ] читается «не
P[пэ]».
Конъюнкцией высказываний P[пэ] и Q[кю] будем называть высказывание, которое истинно тогда и только тогда, когда P[пэ] и Q[кю] истинны. Конъюнкция высказываний P[пэ] и Q[кю] читается «P[пэ] и
Q[кю]».
Дизъюнкцией высказываний P[пэ] и Q[кю] называется высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний P[пэ] и Q[кю]. Дизъюнкция высказываний P[пэ] и Q[кю] читается «P[пэ] или [кю]».
Составим таблицу истинности для операций отрицания, конъюнкции и дизъюнкции.
Конъюнкция высказываний P[пэ] и Q[кю] – это высказывание «P[пэ] и
Q[кю]», принимающее значение «1» в том случае, когда оба высказывания истинны, и значение «0» во всех остальных случаях. Конъюнкция выполняет роль связки «и».
Дизъюнкция высказываний P[пэ] и Q[кю] – это высказывание «P[пэ] или Q[кю]», принимающее значение «0» в том случае, когда оба высказывания ложны, и значение «1» во всех остальных случаях.
Дизъюнкция выполняет роль связки «или».
Слайд 101
Импликацией высказываний P[пэ] и Q[кю] называется высказывание, которое является ложным тогда и только тогда, когда высказывание P[пэ] истинно, а высказывание Q[кю] ложно. При этом P[пэ] называется посылкой, а Q[кю] – следствием
Импликация P[пэ] и Q[кю] читается «если P[пэ], то
Q[кю]», или «из P[пэ] следует Q[кю]», или «P[пэ] достаточно для Q[кю]», или «Q[кю] необходимо для P[пэ]».
Эквиваленцией, или эквивалентностью, высказываний P[пэ] и Q[кю] называется высказывание, которое является истинным тогда и только тогда, когда P[пэ] и Q[кю] либо оба истинны, либо оба ложны. Эквиваленция P[пэ] и Q[кю] читается «P[пэ] равносильно Q[кю]», или «P[пэ] тогда и только тогда, когда
1 2 3 4 5 6 7 8 9
Q[кю]», или «P[пэ] необходимо и достаточно для Q[кю]».
Составим таблицу истинности для операций импликации и эквиваленции.
Перечисленные выше операции – конъюнкция, дизъюнкция, импликация и эквиваленция – применяются к двум высказываниям, то есть являются бинарными операциями. Операция отрицания применяется к одному высказыванию, это унарная операция.
Слайд 102
Переменные, вместо которых можно подставлять конкретные высказывания, называются высказывательными переменными, или переменными высказываниями. Они обозначаются заглавными буквами латинского алфавита с индексами или без индексов. Примеры высказывательных переменных представлены формулой (4.4).
Из исходных высказывательных переменных с помощью операций отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции могут быть образованы различные выражения, называемые формулами.
Сформулируем точное определение формулы алгебры высказываний.
1. Каждая высказывательная переменная есть формула.
2. Если F
1
и F
2
– формулы, то выражения (4.5) также являются формулами.
3. Никаких других формул, кроме получающихся согласно пунктам 1 и 2, нет.
Любая часть формулы, которая сама является формулой, называется подформулой.
Для краткости записи внешние скобки у формулы договариваются опускать.
Количество скобок в записи формулы можно уменьшить, если договориться считать, что операция конъюнкции сильнее операции дизъюнкции, дизъюнкция сильнее импликации, а импликация сильнее эквиваленции. Черта над подформулой, обозначающая знак отрицания, выполняет функцию скобок и позволяет их не ставить.
Пусть дана формула алгебры высказываний (4.6). Если вместо соответствующих переменных подставить некоторые конкретные высказывания, то получится составное высказывание (4.7).
Рассмотрим следующий пример. Формула (4.8) является формулой алгебры высказываний. Формулы (4.9) и (4.10) являются подформулами формулы (4.8).
Слайд 103
Для того чтобы определить значение составного высказывания, требуется подставить символы 0 или 1 соответственно вместо каждого из простых высказываний и выполнить над этими символами все операции, предписываемые формулой.
Представленная на слайде формула задает функцию, множество значений которой можно определить с помощью таблицы истинности, придавая значениям переменных значения 0 и 1. Для формулы, содержащей
n[эн] исходных высказывательных переменных, таблица истинности имеет 2
n
[два в степени эн] строчек.
Заполним таблицу истинности для нашей формулы. Всевозможные системы значений исходных высказывательных переменных представлены в первых трех колонках таблицы восемью строчками.
Далее заполняем столбец, соответствующий первой операции в формуле – импликации. Затем заполняем пятый столбец, соответствующий операции конъюнкции, применяемой к выражениям, указанным в четвертом и третьем столбцах таблицы. Последний столбец определяет значения заданной формулы.
Слайд 104
Введем понятия выполнимой и опровержимой формул алгебры высказываний.
Если существует набор значений высказывательных переменных, на котором формула обращается в истинное высказывание, то формула называется выполнимой.
Если существует набор значений высказывательных переменных, на котором формула обращается в ложное высказывание, то формула называется опровержимой.
Приведенная на слайде формула (4.11) соответствует определению выполнимой формулы, так как на наборе (0, 0, 1)[ноль ноль один] она принимает значение один.
Обратимся к формуле (4.12). Указанная формула удовлетворяет определению опровержимой формулы, так как на наборе (1, 1, 0)[один один ноль] она принимает значение ноль.
Слайд 105
Формула алгебры высказываний называется тождественно истинной, или тавтологией, если она обращается в истинное высказывание при всех наборах значений высказывательных переменных.
Приведенные на слайде формулы (4.13–4.17) являются тождественно истинными. Они выражают основные законы математической логики, к
которым относятся закон тождества, закон исключенного третьего, закон противоречия, а также законы двойного отрицания и контрапозиции.
Докажем, например, что формула (4.17) является тавтологией. Для истинности эквиваленции требуется, чтобы выражения в левой и правой ее частях принимали одинаковые логические значения. Импликация в левой части формулы (4.17) обращается в ложное высказывание в том и только в том случае, когда F = 1[эф равно единице], а G = 0[же равно нулю]. То же самое можно сказать и про импликацию в правой части этой формулы. Таким образом, на любых наборах значений высказывательных переменных логические значения обеих импликаций совпадают, а значит, формула (4.17) является тавтологией.
Формула алгебры высказываний называется тождественно ложной, или противоречием, если она обращается в ложное высказывание при всех наборах значений высказывательных переменных.
Формулы (4.18) представляют собой примеры тождественно ложных формул.
Слайд 106
Введем понятие логического следствия формул.
Пусть формулы F
1
,…, F
m
[эф один и т.д. эф эм] и формула G[жэ] зависят от одних и тех же переменных. Если для всех наборов значений переменных, для которых формулы F
1
,…, F
m
[эф один и т.д. эф эм] одновременно обращаются в истинные высказывания, формула G[жэ] также обращается в истинное высказывание, то формула G[жэ] называется логическим следствием формул F
1
,…, F
m
[эф один и т.д. эф эм]. Формулы
F
1
,…, F
m
[эф один и т.д. эф эм] называются посылками для логического следствия G[жэ]. Выражение (4.19) используется для обозначения того, что формула G[жэ] является логическим следствием формул F
1
,…, F
m
[эф один и т.д. эф эм].
Докажем, например, что формула (4.17) является тавтологией. Для истинности эквиваленции требуется, чтобы выражения в левой и правой ее частях принимали одинаковые логические значения. Импликация в левой части формулы (4.17) обращается в ложное высказывание в том и только в том случае, когда F = 1[эф равно единице], а G = 0[же равно нулю]. То же самое можно сказать и про импликацию в правой части этой формулы. Таким образом, на любых наборах значений высказывательных переменных логические значения обеих импликаций совпадают, а значит, формула (4.17) является тавтологией.
Формула алгебры высказываний называется тождественно ложной, или противоречием, если она обращается в ложное высказывание при всех наборах значений высказывательных переменных.
Формулы (4.18) представляют собой примеры тождественно ложных формул.
Слайд 106
Введем понятие логического следствия формул.
Пусть формулы F
1
,…, F
m
[эф один и т.д. эф эм] и формула G[жэ] зависят от одних и тех же переменных. Если для всех наборов значений переменных, для которых формулы F
1
,…, F
m
[эф один и т.д. эф эм] одновременно обращаются в истинные высказывания, формула G[жэ] также обращается в истинное высказывание, то формула G[жэ] называется логическим следствием формул F
1
,…, F
m
[эф один и т.д. эф эм]. Формулы
F
1
,…, F
m
[эф один и т.д. эф эм] называются посылками для логического следствия G[жэ]. Выражение (4.19) используется для обозначения того, что формула G[жэ] является логическим следствием формул F
1
,…, F
m
[эф один и т.д. эф эм].
Представленные на слайде выражения (4.20–4.23) задают примеры логического следствия формул.
Из сформулированного определения вытекает алгоритм проверки формул на логическое следствие. Нужно составить таблицу истинности для формул F
1
,…, F
m
[эф один и т.д. эф эм] и формулы G[жэ]. Если в каждой строке таблицы, в которой все формулы F
1
,…, F
m
[эф один и т.д. эф эм] принимают значение 1, формула G[жэ] также принимает значение 1, то формула G[жэ] является логическим следствием формул F
1
,…, F
m
[эф один и т.д. эф эм]. Если же в некоторой строке таблицы истинности все формулы
F
1
,…, F
m
[эф один и т.д. эф эм] принимают значение 1, а формула G[жэ] принимает значение 0, то формула G[жэ] не является логическим следствием формул F
1
,…, F
m
[эф один и т.д. эф эм].
Слайд 107
Рассмотрим пример логического следствия формулы.
Представленное на слайде соотношение (4.24) означает, что всякий раз, когда импликация в левой части обращается в истинное высказывание, дизъюнкция в правой части также должна обращаться в истинное высказывание.
В перечне (4.25) указаны наборы значений переменных, обращающие в единицу левую часть соотношения (4.24). Действительно, если следствие импликации принимает значение один, то импликация истинна. Таким образом, если переменная R[эр] принимает значение один, то при любых значениях переменных P[пэ] и Q[кю] импликация равна единице. Если же переменная R[эр] принимает значение нуль, посылка также должна быть равна нулю. А дизъюнкция принимает значение нуль только случае, когда
P[пэ] и Q[кю] равны нулю.
На каждом из приведенных наборов правая часть соотношения (4.24) также обращается в единицу. Действительно, дизъюнкция принимает нулевое значение только в том случае, когда все участвующие в ней
элементы являются нулями. Но это возможно лишь при значениях переменных, указанных в равенствах (4.26). Такого набора значений нет в перечне (4.25). Следовательно, при обращении в единицу левой части соотношения (4.24) его правая часть также обращается в единицу.
Слайд 108
Рассмотрим на примере, как решается вопрос о том, является ли одна из двух данных формул следствием другой.
Пусть заданы формулы (4.27) и (4.28). Формула (4.28) представляет собой дизъюнкцию, а значит, она обращается в ноль только в случае, когда значения всех переменных равны нулю. Данная ситуация отражена в равенствах (4.29). Но при этих значениях переменных формула (4.27) также обращается в ноль. Поэтому мы можем утверждать, что всякий раз, когда формула (4.27) обращается в единицу, формула (4.28) тоже обращается в единицу. Таким образом, формула (4.28) является логическим следствием формулы (4.27).
С другой стороны, при значениях переменных, указанных в равенствах
(4.30), формула (4.28) обращается в единицу, а формула (4.27) – в ноль. Это говорит о том, что формула (4.27) не является логическим следствием формулы (4.28).
Слайд 109
Рассмотрим формулы (4.31), (4.32), (4.33), (4.34) и (4.35). Поставим задачу расположить их таким образом, чтобы после каждой формулы стояли все логически из нее вытекающие формулы.
Из определения логического следования получаем, что тождественно ложная формула является посылкой для любой формулы, а тождественно истинная формула является следствием для любой системы посылок.
Для решения задачи составим таблицу значений заданных формул. Из таблицы видно, что формулы (4.31) и (4.34) принимают одинаковые значения, а формула (4.35) является тождественно ложной. На первое место в
Слайд 108
Рассмотрим на примере, как решается вопрос о том, является ли одна из двух данных формул следствием другой.
Пусть заданы формулы (4.27) и (4.28). Формула (4.28) представляет собой дизъюнкцию, а значит, она обращается в ноль только в случае, когда значения всех переменных равны нулю. Данная ситуация отражена в равенствах (4.29). Но при этих значениях переменных формула (4.27) также обращается в ноль. Поэтому мы можем утверждать, что всякий раз, когда формула (4.27) обращается в единицу, формула (4.28) тоже обращается в единицу. Таким образом, формула (4.28) является логическим следствием формулы (4.27).
С другой стороны, при значениях переменных, указанных в равенствах
(4.30), формула (4.28) обращается в единицу, а формула (4.27) – в ноль. Это говорит о том, что формула (4.27) не является логическим следствием формулы (4.28).
Слайд 109
Рассмотрим формулы (4.31), (4.32), (4.33), (4.34) и (4.35). Поставим задачу расположить их таким образом, чтобы после каждой формулы стояли все логически из нее вытекающие формулы.
Из определения логического следования получаем, что тождественно ложная формула является посылкой для любой формулы, а тождественно истинная формула является следствием для любой системы посылок.
Для решения задачи составим таблицу значений заданных формул. Из таблицы видно, что формулы (4.31) и (4.34) принимают одинаковые значения, а формула (4.35) является тождественно ложной. На первое место в