Основные операции над высказываниями.

 

Отрицание.

Высказывание , которое истинно, если р ложно, и ложно, если р истинно, называется отрицанием.

Таблица истинности:

р
0	1
1	0

 

Пример:

р - число 5 делится на 3. р = 0.

 - число 5 не делится на 3. = 1.

Конъюнкция (логическое умножение).

Пусть даны два высказывания р и q.

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

Задается союзом И. Обозначение .

Таблица истинности:

р	q
1	1	1
1	0	0
0	1	0
0	0	0

 

Пример:

А) Высказывание р: 15 делится на 3 - истина.

Высказывание q: 15 делится на 5 - истина.

: 15 делится на 3 и 5.- это истинное высказывание

Б) Высказывание р: 15 делится на 3 - истина.

Высказывание q: 15 делится на 6 - ложь.

: 15 делится на 3 и 6.- это ложное высказывание

 

3) Дизъюнкция (логическое сложение).

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

 Задается союзом ИЛИ. Обозначение .

Таблица истинности:

р	q
1	1	1
1	0	1
0	1	1
0	0	0

Пример:

А) Высказывание р: 15 делится на 3 - истина.

Высказывание q: 15 делится на 5 - истина.

: 15 делится на 3 или 5.- это истинное высказывание

Б) Высказывание р: 15 делится на 4 - ложь.

Высказывание q: 15 делится на 6 - ложь.

: 15 делится на 4 или 6.- это ложное высказывание

В) Высказывание р: 15 делится на 3 - истина.

Высказывание q: 15 делится на 6 - ложь.

: 15 делится на 3 или 5.- это истинное высказывание

 

Импликация.

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

 ЕСЛИ р, ТО q. Обозначение .

Таблица истинности:

р	q
1	1	1
1	0	0
0	1	1
0	0	1

 

Пример:

А) Высказывание р: 15 делится на 3 - истина.

Высказывание q: 15 делится на 5 - истина.

: Если 15 делится на 3, то 15 делится на  5.- это истинное высказывание

Б) Высказывание р: 15 делится на 3 - истина.

Высказывание q: 15 делится на 6 - ложь.

 Если 15 делится на 3, то 15 делится на 6.- это ложное высказывание

В) Высказывание р: 15 делится на 4 – ложь.

Высказывание q: 15 делится на 6 - ложь.

 Если 15 делится на 4, то 15 делится на 6.- это истинное высказывание

5) Эквиваленция.

6) Эквиваленцией двух высказываний р и q называется высказывание, которое истинно, если оба высказывания принимают одинаковые значения.

 В словесной формулировке: тогда и только тогда; необходимо и достаточно; если и только если. Обозначение

 

Таблица истинности:

 

р	q
1	1	1
1	0	0
0	1	0
0	0	1

 

Пример:

р - треугольник равнобедренный.

q - углы при основании треугольника равны.

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

 

7) Стрелка Пирса -  ↓.

Логическая операция задается таблицей:

 

р	q	р ↓ q
1	1	0
1	0	0
0	1	0
0	0	1

 

Стрелка Пирса является отрицанием дизъюнкции.

 

8) Штрих Шеффера -  |.

 

Логическая операция задается таблицей:

 

р	q	р | q
1	1	0
1	0	1
0	1	1
0	0	1

 

Штрих Шеффера является отрицанием конъюнкции.

Формулы.

Используя определенные выше логические операции (логические связки),  мы можем конструировать все более сложные высказывания, которые будем записывать в виде формул.

Дадим декларативное определение формулы.

1) 0 и 1 –это формула.

2) Простые высказывания (р) и  (q) есть формула.

3) Если () и (  ) - формулы, то () – формула; ()  () - формула; ()  () - формула; ()  () – формула; ()  () – формула.

4) Других формул нет.

Пример:

() ()-формула.

Доказательство:

(р) и (q)-формулы (по 2), - формула (по 3), ()- формула (по 3), -формула (по 3), () -формула (по 3).

Соглашение о скобках.

1) Элементарные высказывания в скобки заключать не будем.

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

3) связывает сильнее, чем , , .

4) связывает сильнее, чем  и .

5)  связывает сильнее, чем .

Пример:

Вместо ((р)  (q)) ((r)  ()) пишем р q r . Знак конъюнкции можно опускать: р q r .

Булевы функции.

Так как каждое высказывание задается на множестве {0,1}, то любая формула отображает свои значения  на множество {0,1}. Таким образом, формула логики высказываний определяет на множестве {0,1} логическую функцию со значениями 0,1. Эти функции получили название булевых.

Равносильные формулы.

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

Обозначение равносильности:

Пример:

Φ =  и Φ = q.

Их таблицы истинности:

 

р	q	Ф =		Ф2 = q
1	1	1	0	1
1	0	0	0	0
0	1	1	1	1
0	0	1	1	1

 

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

Основные равносильности.

1) р.

Коммутативность:

2) р q q р.

3) .

Ассоциативность:

4) (р q) r р  (q r).

5) () r р  (q r).

  Дистрибутивность:

6) р  (q r). р r.

7) р  (q r) (р q)  (р r).

  Законы Де-Моргана:

8) .

9) .

  Поглощение:

10) р р р.

11) р р р.

Операции с 0 и 1

12) р 0 0.

13) р 1 р.

14) р 0 р.

15) р 1 1.

  Связь с отрицанием

16) р 0.

17) р 1.

  Связь импликации и эквиваленции с другими операциями

18) q.

19) ()  ().

 

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

 

 Используются равносильности при преобразованиях формул.

Пример преобразований с использованием равносильностей.:

r (снимаем эквиваленциию по 19)                                                       

(() r )(r ()) снимаем импликации по 18)

 ( r)( q)  (по законам де Моргана)

( r)( q) (снимаем двойные отрицания по 1)

(р r)(q q)  (в первой скобке выносим за скобку по 6, во второй скобке по 11)   (р )  (q )   (по 6)

(р ) (q )  (по 16)

  (р ) (0 )  (по 14)

(р ) ( )  (по 6)

  р  р (по 10 и 16)

  р  0  (по 14 и 6)

(р 1) 1 .