Алгебра высказываний.

изд.- Владивосток: Изд-во ВГУЭС, 2001. 2.Шишмарев Ю.Е. Дискретная математика: Конспект лекций.

Ч.2.-.Владивосток: Изд-во ВГУЭС, 2002. 3.Емцева Е.Д., Солодухин К.С. Дискретная математика: Курс лекций. Ч.3.-Владивосток: Изд-во ВГУЭС, 2002. 4. Шишмарев Ю.Е., Емцева Е.Д., Солодухин К.С. Дискретная математика. Сборник задач. Ч.1. – 2-е изд., испр. и доп. - Владивосток: Изд-во ВГУЭС, 2002. 5.Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. 6.Лекции по теории графов/ Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. 7. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика.- М.: ФИМА, МЦНМО, 2006

русского языка, о котором можно сказать, истинно оно или ложно.

Высказывания мы будем обозначать заглавными буквами латинского алфавита, возможно с индексами:

Если высказывание А истинно, мы будем писать А=1; если высказывание А ложно, мы будем писать А=0.

Примеры
1. А=«два умножить на два равно семи»
2. В=«два плюс два равно 4»
3. С=«если сентябрь – весенний месяц, то 5*5=25»
4.D=«число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3»
5.E=«если после четверга следует пятница, то в году 13 месяцев»
A=0
B=1
C=?
D=1
E=?

и обозначается
Задается действие отрицания с помощью таблицы истинности:
 

Например, "2*2=4 и 5+3=9"
Определение 2
Высказывание "А и В" называется

конъюнкцией (или логическим умножением) высказываний А и В.
Конъюнкция имеет много обозначений:

Конъюнкция задается с помощью таблицы истинности:

 

 

 

 

Конъюнкция

Например, "2*2=4 или 5+3=9".

Определение 3
Высказывание "А или В" называется дизъюнкцией

(или логическим сложением) высказываний А и В
и обозначается A v B

Дизъюнкция задается с помощью таблицы истинности:

 

Дизъюнкция

и только тогда, когда В".
Например, треугольник является равносторонним тогда и

только тогда, когда все его углы равны между собой.
Синонимами служат фразы:
"А в том и только в том случае, когда В",
"А необходимо и достаточно для того, чтобы выполнялось В",
"А равносильно В",
"А эквивалентно B".

Определение 4
Высказывание "А равносильно В" называется эквивалентностью высказываний А и В и обозначается:

Эквивалентность

то В".
Например, если две прямые параллельны третьей, то они параллельны

между собой.
Синонимами служат следующие фразы:
"из А следует В",
"В является следствием А",
"А влечет В",
"А достаточное условие для В",
"В необходимое условие для А" и т.п.

Определение 5
Высказывание "если А, то В" называется импликацией высказываний А и В
и обозначается:

В этой ситуации высказывание А называется посылкой, а В – заключением.

Импликация

будет четверг"
D=1
2. Y="если после четверга следует пятница, то

после пятницы следует воскресенье“
Y=0
3. Х="если два плюс два равно пяти, то три плюс два равно десяти“
X=1
4. Z="если 1+1=3, то после пятницы следует суббота“
Z=1

импликации и, возможно, помогут получше ее запомнить:

1)

если посылка ложна, то импликация всегда истинна, независимо от заключения, то есть

2) если заключение истинно, то импликация также истинна, независимо от посылки, то есть

Или обобщающая фраза: “из истины ложь не следует”

Импликация

логической (или булевой) переменной.
Обозначаться логические переменные будут заглавными латинскими буквами

с индексами или без них:

имеет вид

 

Если высказывание F построено из логических переменных

, то будем обозначать это высказывание:

Теорема
Наборов длины n из 0 и 1 существует

подразумевает скобки.
3) Конъюнкция связывает сильнее, чем дизъюнкция.
Например,
4) Дизъюнкция связывает

сильнее, чем импликация.
Например,

5) Импликация связывает сильнее, чем эквивалентность.
Например,

ирригационные канавы; если хлеба не уцелеют, то фермеры обанкротятся и

оставят фермы.»
Решение
Пусть
А=«хлеба уцелеют»
B=«будут вырыты ирригационные канавы»
С=«фермеры обанкротятся»
D=«фермеры оставят фермы».
Тогда

(или просто равными), если для любого набора
имеет место равенство:

Обозначим

Другими словами, два высказывания равны, если у них совпадают таблицы истинности.

9)
10)
11)
12)
13)
14)
15)
Дистрибутивные законы:
Без названия:
16)
17)

2
Высказывание называется дизъюнктивной нормальной формой (ДНФ), если оно представляет собою

дизъюнкцию элементарных конъюнкций.

Общий вид ДНФ:

3. Дизъюнктивные нормальные формы (ДНФ)

от импликации и эквивалентности, используя законы
16), 17)
2) Донести отрицания до

переменных, используя законы Моргана.
3) Раскрыть скобки, используя дистрибутивные законы.
4) Упростить полученное высказывание.

1
Пусть

 – некоторое множество логических переменных. Элементарная конъюнкция, в которую входят все логические переменные, называется полной элементарной конъюнкцией относительно множества X .

Пример

ее элементарные конъюнкции являются полными.
Примеры








СДНФ

Высказывание, не являющееся

тождественно ложным, приводимо к СДНФ.
Правило приведения высказывания к СДНФ
СДНФ содержит столько полных элементарных конъюнкций, сколько единиц в последнем столбце таблице истинности.
Вид каждой полной элементарной определяется соответствующим набором значений переменных, а именно, если переменная принимает значение 0, то над ней в полной элементарной конъюнкцией ставится отрицание, иначе – отрицание не ставится.

Есть новости?
- Да, шеф. Поступили сообщения от инспекторов.
Торранс установил,

что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет.
Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи.
Инспектор Люка просил передать Вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет.
Затем звонила …
- Все. Спасибо. Этого достаточно. – Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.»
Что знал Мегрэ?

получим высказывание












Так как

, то Этьен - убийца

изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников,

а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал.
Каждый переключатель X имеет только два состояния: замкнутое (X=1) и разомкнутое(X=0). .

соревнования тремя судьями при условиях: судья засчитавший результат, нажимает имеющуюся

в его распоряжении кнопку, а судья, не засчитывающий результат, кнопки не нажимает. В случае, если кнопки нажали не менее двух судей, загорается лампочка (положительное решение судей принятое большинством голосов).