2. Конъюнкция и дизъюнкция высказываний

Пусть А и В – произвольные высказывания. Образуем из них с помощью союза «и» составное высказывание. Такое высказывание называют конъюнкцией (от латинского слова «единение»).

Обозначают (читают:А и В).

Конъюнкцией высказываний А и В называется высказывание , которое истинно, когда оба высказывания истинны, и ложно, когда хотя бы одно из этих высказываний ложно.

А	В
1	1	1
1	0	0
0	1	0
0	0	0

Определение конъюнкции можно записать с помощью таблицы, называемой таблицей истинности конъюнкции.

Пример 1. Высказывание «Мурманск находится за Полярным кругом и все студенты МГПУ – живут в общежитии» ложно.

Пример 2. Математическая запись «»является конъюнкцией двух высказываний «» и «».

Пусть А и В – произвольные высказывания. Образуем из них с по­мощью союза «или» составное высказывание. Полученное высказыва­ние называют дизъюнкцией (от латинского слова «разделение»).

Обозначают (читают: «А или В»).

Дизъюнкцией высказываний А и В называется выска­зывание , которое истинно, когда истинно хотя бы одно из этих высказываний, и ложно, когда оба высказывания ложны.

Таблица истинности дизъюнкции:

A	B
1	1	1
1	0	1
0	1	1
0	0	0

Пример 1. Высказывание «Мурманск находится за Полярным кругом или все студенты МГПУ – живут в общежитии» истинно.

Пример 2. Математическая запись «» означает дизъюнкцию двух высказываний «» или «».

Определения конъюнкции и дизъюнкции можно обобщить на несколько со­ставляющих их высказываний.

Конъюнкцией n высказываний называется предложение вида , которое истинно тогда и только тогда, когда истинны все составляющие его высказывания.

Дизъюнкцией n высказываний называется предложение вида , которое ложно тогда и только тогда, когда ложны все состав­ляющие его высказывания.

2. Импликация и эквиваленция высказываний

Пусть А и В – произвольные высказывания. Образуем из них с помощью логической связки «если…, то…» составное высказывание. Такое высказывание называют импликацией (от латинского слова «…»).

Обозначают (читают:если А, то В или из А следует В).

Импликацией высказываний А и В называется высказывание , которое ложно только тогда, когда высказываниеА истинно, а В ложно, во всех остальных случаях истинно.

А	В
1	1	1
1	0	0
0	1	1
0	0	1

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

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

Пример 1. Высказывание «Если Мурманск находится за Полярным кругом, то все студенты МГПУ – живут в общежитии» ложно.

Пусть А и В – произвольные высказывания. Образуем из них с помощью логической связки «тогда и только тогда, когда…» составное высказывание. Такое высказывание называют эквиваленцией (от латинского слова «…»).

Обозначают (читают:А тогда и только тогда, когда В или А эквивалентно В или А равносильно В).

Эквиваленцией высказываний А и В называется высказывание , которое истинно только тогда, когда высказыванияА и В одновременно истины или одновременно ложны, во всех остальных случаях ложно.

А	В
1	1	1
1	0	0
0	1	0
0	0	1

Связкой эквиваленции могут быть соединены любые, в том числе и независимые друг от друга по смыслу высказывания.

Пример. Высказывание «Мурманск находится за Полярным кругом тогда и только тогда, когда все студенты МГПУ – живут в общежитии» ложно.

Логические связки позволяют из простых высказываний получать новые, сколь угодно сложные высказывания.

Запись сложного высказывания в виде простых высказываний, соединенных логическими связками называется логической формулой.

Придерживаются следующего порядка выполнения операций: приоритет имеет отрицание, затем на одном уровне конъюнкция и дизъюнкция, потом импликация, и самая последняя – эквиваленция.

Для сложных высказываний, т.е. таких, где присутствуют несколько логических связок, также применяют таблицы истинности, где перебирают все возможные значения истинности составляющих высказываний – простых компонент (высказываний, которые нельзя представить как результат действия логических операций) и элементарных формул. Такая таблица содержит строк, гдеп – количество простых компонент.

Таблицу истинности составляют, разбивая сложное высказывание на более простые и добавляя вспомогательные столбцы со значениями истинности этих составляющих.

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

Высказывания содержат две простые компоненты А и В, поэтому таблица истинности будет содержать строк.

1	1	0	0	1	0	0
1	0	0	1	0	1	1
0	1	1	0	0	1	1
0	0	1	1	0	1	1

Про высказывания вида и говорят, что они равно­сильны, и пишут . Считают, что высказывания равносильны, если они одновременно ис­тинны, либо одновременно ложны. Другими словами, если их значе­ния истинности совпадают при одинаковых наборах значений выска­зываний А и В.

Аналогично можно доказать, что имеет место равносильность , т.е. отрицание дизъюнкции равносильно конъюнкции отрицаний.

Эти равносильности носят название законов де Моргана.

Пример 2. Доказать закон контрапозиции:

.

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

Высказывание содержит три простые компоненты А, В, С, поэтому таблица истинности будет содержать строк.

А	В	С
1	1	1	1	1	1	1	1
1	1	0	1	0	0	0	1
1	0	1	0	1	0	1	1
1	0	0	0	1	0	0	1
0	1	1	1	1	1	1	1
0	1	0	1	0	0	1	1
0	0	1	1	1	1	1	1
0	0	0	1	1	1	1	1

Получили что, какие бы значения ни принимали простые компоненты, все высказывание принимает только значение – истинно. Таким образом, высказывание тождественно истинно. Справедливость данного закона доказана.