Файл: В. Ф. Пономарев математическая логика.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.01.2024

Просмотров: 316

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Алгоритм вывода по принципу резолюции, 69

Правила подстановки, 52, 114

Принцип резолюции, 68,126

Тождественно истинные формулы, 45, 112



F=F1(F2)F3F4;

4) убрать скобки, охватывающие формулу отрицания, так как опера­ция дизъюнкции будет исполняться только после выполнения операции отрицания:

F=F1F2F3F4;

Итак, последовательность исполнения операций после задания значений пропозациональных переменных следующая: сначала необходимо определить значение формулы (F2), затем (F1(F2)) затем ((F1(F2))F3) и, наконец, (((F1(F2))F3)F4)

Пример: Дана формула F=F1F2F3F1F3F1. Необходимо расставить все скобки.

1) поставить скобки на формулу, реализующую операцию отрицания:

F1F2F3(F1)F3F1;

2) поставить скобки на формулу, реализующую операцию конъюнкции:

F=((F1F2)F3)(F1)F3F1;

3) поставить скобки на формулу, реализующую операцию дизъюнкции:

F=(((F1F2)F3)(F1))F3F1;

4) поставить скобки на формулу, реализующую операцию импликации:

F=((((F1F2)F3)(F1))F3)F1;

5) поставить скобки на формулу, реализующую операцию эквиваленции:

F=(((((F1F2)F3)(F1))F3)F1).

1.1.3 Законы алгебры логики

Две формулы F1 и F2 называются равносильными, если они имеют одинаковое значение “и” или “л” при одинаковых наборах пропозициональных переменных, включаемых в F1 и F2, т.е. F1 = F2 . Если две формулы равносильны, то они эквивалентны, т.е. (FiFi).

Если формула F имеет вхождением подфор­мулу Fi, для которой существует эквивалентная подформула Fj, т.е. FiFj, то возможна подстановка всюду в формулу F вместо формулы Fi подформулу Fj без нарушения истинности формулы F.

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

Наименование закона
Равносильные формулы

Fi=Fj

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

(F1F2)=(F2F1); (F1F2)=(F2F1)

Ассоциативности
F1(F2F3)=(F1F2)F3;

F1(F2F3) = (F1F2) F3

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

F1(F2 F3)=(F1F2)(F1F3);

F1(F2F3)=F1F2F1F3

Идемпотентности

FF = F; FF = F

Исключенного третьего

FF = и;

Противоречия
FF = л

Де Моргана
(F1F2) = F1F2; (F1F2) = F1F2

.

Поглощения
F1(F1F2) = F1; F1(F1F2) = F1

Дополнения
(F) = F

Свойства констант
Fл = F; Fл= л;

Fи = и; Fи = F
1   2   3   4   5   6   7   8   9   ...   14


С

F1
F2
12
13

1
2
3
4

Л
Л
Л
Л

Л
И
Л
Л

И
Л
Л
И

И
И
И
И



праведливость некоторых законов подтверждается в примерах таблицами истинности.

Пример: F1(F1F2) = F1

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

закон поглощения.


П

F1
F2
12
13

1
2
3
4

Л
Л
Л
Л

Л
И
И
Л

И
Л
И
И

И
И
И
И



ример: F1  (F1F2) = F1

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

второй закон поглощения.

П

F1
F2
 (12)
12

1
2
3
4

Л
Л
И
И

Л
И
Л
Л

И
Л
Л
Л

И
И
Л
Л



ример
: (F1F2) = F1F2

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

закон де Моргана.

П

F1
F2
 (12)
12

1
2
3
4

Л
Л
И
И

Л
И
И
И

И
Л
И
И

И
И
Л
Л



ример: (F1F2) = F1F2

Сравните значения логических

функций в третьем и четвертом

столбцах. Так можно проверить

второй закон де Моргана..


Пример: F1(F2 F3)=(F1F2)(F1F3).



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

F1

F2
F3
23
14
12
13
67

1
2
3
4
5
6
7
8

Л
Л
Л
Л
Л
Л
Л
Л

Л
Л
И
Л
Л
Л
И
Л

Л
И
Л
Л
Л
И
Л
Л

Л
И
И
И
И
И
И
И

И
Л
Л
Л
И
И
И
И

И
Л
И
Л
И
И
И
И

И
И
Л
Л
И
И
И
И

И
И
И
И
И
И
И
И



Пример: F1(F2F3)=F1F2F1F3


Сравните значения логических функций в пятом и восьмом столбцах. Так можно проверить второй закон дистрибутивности.




F1
F2
F3
23
14
12
13
67

1
2
3
4
5
6
7
8

Л
Л
Л
Л
Л
Л
Л
Л

Л
Л
И
И
Л
Л
Л
Л

Л
И
Л
И
Л
Л
Л
Л

Л
И
И
И
Л
Л
Л
Л

И
Л
Л
Л
Л
Л
Л
Л

И
Л
И
И
И
Л
И
И

И
И
Л
И
И
И
Л
И

И
И
И
И
И
И
И
И

1.1.4 Эквивалентные преобразования формул

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

П



F1
F2
12
12
(12)

1
2
3
4
5

Л
Л
И
И
И

Л
И
И
И
И

И
Л
Л
Л
Л

И
И
И
И
И



ример 26: F1F2 = F1F2 = (F1F2).
Сравните значения логических функций в третьем, четвертом и пятом столбцах. То есть

операцию импликации всегда можно заместить исполнением операций дизьюнкции и отрицания или коньюнкции и отрицания.
Пример: F1F2 = (F1F2)(F2F1) = (F1F2)(F2F1) =

= ((F1F2) (F2F1)).


F1
F2
F1F2
F1F2
F2F1
45
F1F2
F2F1
78
78
10

1
2
3
4
5
6
7
8
9
10
11

Л
Л
И
И
И
И
И
И
И
Л
И

Л
И
Л
И
Л
Л
И
Л
Л
И
Л

И
Л
Л
Л
И
Л
Л
И
Л
И
Л

И
И
И
И
И
И
И
И
И
Л
И

Смотрите также файлы