Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
МАТ_ ЛОГИКА / Математическая логика_Лекция 2.ppt
Скачиваний:
62
Добавлен:
06.06.2015
Размер:
456.19 Кб
Скачать

МАТЕМАТИЧЕСКАЯ ЛОГИКА

Лекция 2. Истинностные функции логики высказываний

1.Истинностные значения и истинностные таблицы формул логики высказываний

2.Отношение равносильности формул

3.Истинностные функции

4.Совершенные нормальные формы истинностных функций

5.Полные системы истинностных функций

6.Классификация формул логики высказываний

Истинностные значения формул логики высказываний

Истинностные таблицы формул логики высказываний

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

Отношение равносильности формул

Отношение равносильности формул

Истинностные функции

Логические функции одной переменной

x

F1

F2

 

F3

 

F4

 

 

 

 

 

 

 

 

0

0

0

 

1

 

1

 

 

 

 

1

0

1

 

 

 

0

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Логические функции двух переменных

Двухместных истинностных функций - 16

x1

x2

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14 F15

F16

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Число п-местных истинностных функций

2

(2

n

)

равно

 

 

 

 

 

Дизъюнктивно-нормальная форма

ДНФ является логической суммой элементарных конъюнкций.

Совершенная ДНФ логическая сумма элементарных конъюнкций, в каждой из которых присутствуют все переменные данной функции.

Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделённых операциями конъюнкции (дизъюнкции):

s

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

xi

 

 

 

 

 

 

 

 

 

 

x x

 

x3

yi

 

yi xi

 

2

 

 

1

 

 

 

 

 

, где

или

, например

- элементарная

i 1 конъюнкция;

 

 

 

 

 

 

 

 

 

 

 

s

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

yi

,

где

или ,например

- элементарная

 

 

yi xi

 

 

xi

x1

x2 x3

i 1

дизъюнкция;