1.Алгебра высказываний; пропозициональные связки и формы, истинностные таблицы
Высказывание – повествовательное предложение, о котором можно сказать, истинно оно или ложно. Значение «истинно» и «ложно» обычно обозначаются 1 или 0, или И и Л.
Содержательно логические операции обычно интерпретируют следующим образом:
отрицание (инверсия)¬ (− ) − «не»
дизъюнкция
− «или»
конъюнкция & (А&B или A.В) − «и»
импликация → − «если … , то»
эквивалентность ~ − «тогда и только тогда» (или «эквивалентно»)
приоритеты
по выполнению действий: ¬, &,
,
→, ~ .
Символы
¬, &,
,
→, ~ наз-ся пропозициональными(или
логическими)
связками.
Буквы, обозначающие высказывания, наз-ся
пропозициональными
буквами.
Осмысленные формулы, составленные из
пропозициональных букв, пропозициональных
связок, а также скобок, указывающих
порядок выполнения операций, наз-ся
пропозициональными
формами(ПФ).
Операции логики высказываний можно задать с помощью табл.:
А
В ¬А А
В А&B
A→B
A~B
0 0 I 0 0 I I
0 I I I 0 I 0
I 0 0 I 0 0 0
I I 0 I I I I
Используя эту таблицу можно получить истинностную таблицу для произвольной ПФ.
2.Алгебра высказываний; тавтологии и противоречия
Сложное высказывание, истинное при любых значениях входящих в него элементарных высказываний, называется тавтологией. Отрицание тавтологией есть противоречие. Если ПФ не является противоречием, то она наз-ся выполнимой. Из тавтологий получаются высказывания, истинные по форме, а из противоречий – высказывания, ложные по форме(а не по содержанию).
Если А – тавтология, то ¬А – противоречие. И наоборот.
Если А и А→В – тавтологии, то В – тавтология.
Если А→В и А→¬В – тавтологии, то А – противоречие.
Если в тавтологии вместо пропозициональных букв подставить произвольные ПФ, то снова получится тавтология.
3.Алгебра высказываний; логическая эквивалентность и логическое следствие
Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности" ~.
Логическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом "следовательно" → и выражается словами ЕСЛИ … , ТО …
4. Алгебра высказываний; дизъюнктивная и конъюнктивная нормальные формы
Дизъюнктивной нормальной формой(ДНФ) наз-ся дизъюнкция элементарных конъюнкций. При этом допускается, что может быть всего одно дизъюнктивное слагаемое.
Теорема. Всякая истинностная функция F порождается некоторой ДНФ
Конъюнктивной нормальной формой(КНФ) наз-ся конъюнкция элементраных дизъюнкций. При этом допускается, что может быть всего один конъюнктивный сомножитель.
Теорема. Всякая истинностная функция F порождается некоторой КНФ.