Доведення теоретико-математичних тотожностей і тверджень

Завдання: Довести тотожність: ;

Доведення:

1)

2)

3) ;

Побудова т аблиці істинності висловлень

4.1. Теоретичні відомості

 

Під висловленням розуміють пропозицію людської мови, про яку можна сказати, істинна вона або хибна. Пізніше стане ясно, чому тут говориться не про визначення, а про поняття висловлення. А надалі в нас з'явиться можливість дати точне визначення висловлення. Висловлення позначаються великими буквами латинського алфавіту, можливо з індексами:  . Якщо висловлення А є істинним то пишуть А =1, інакше пишуть А =0.

Задається дія заперечення за допомогою таблиці істинності:

 

0	1
1	0

Кон’юнкція задається за допомогою таблиці істинності:

 

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

Диз'юнкція задається за допомогою таблиці істинності:

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

Еквівалентність задається таблицею істинності:

 

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

 

Задається імплікація таблицею істинності:

 

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

Побудовання таблиці істинності висловлень

 

Завдання: Побудуйте таблиці істинності для висловлювання ;

Відзначимо, відповідно до пріоритетів виконання операцій , кроки, за якими буде побудована таблиця істинності висловлень:

                                                                          

B	D	E	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	F
0	0	0	1	0	0	0	0	1	0	0	1	0	0	1	1
0	0	1	0	0	0	0	0	1	0	0	1	0	0	1	1
0	1	0	1	0	0	0	1	1	0	0	1	0	0	1	1
0	1	1	0	0	0	0	0	1	0	1	0	0	1	1	1
1	0	0	1	0	0	1	0	0	1	0	1	0	0	0	0
1	0	1	0	0	0	0	0	1	0	0	1	0	0	1	1
1	1	0	1	1	1	1	1	1	0	0	1	0	0	0	1
1	1	1	0	1	1	0	0	0	1	1	0	1	1	1	1

Розв‘язок:

Побудова диз'юнктивної нормальної форми (ДНФ)

Теоретичні відомості

Визначення. Нехай F – висловлення і .

 

Визначення.  у тому і тільки в тому випадку, коли .

Визначення. Кон’юнкція логічних змінних або їх заперечень називається елементарною кон’юнкцією. Загальний вигляд елементарної кон’юн­кції

.

Визначення. Висловлення називається диз'юнктивною нормальною формою, якщо воно є диз'юнкцією елементарних кон’юнкцій. загальний вигляд ДНФ

,

 

де кожна , у свою чергу, є елементарною кон’юнкцією.

Теорема. Будь-яке висловлення рівносильне диз'юнктивній нормальній формі (говорять ще так: “Будь-яке висловлення зводиться до ДНФ”).

Основні логічні тотожності:

1) – ідемпотентність диз'юнкції;

2) – ідемпотентність кон’юнкції;

3) – комутативність диз'юнкції;

4) – комутативність кон’юнкції;

5) – асоціативність диз'юнкції;

6) – асоціативність кон’юнкції;

7) – дистрибутивність кон’юнкції щодо диз'юнкції;

8) – дистрибутивність диз'юнкції щодо кон’юнкції.

9) – перший закон Моргана.

10) – другий закон Моргана.

11) – закон подвійного заперечення.

12) – закон протиріччя.

13) – закон виключення третіх.

14) .

15) .

16) .

Тотожності, що містять константи:

17) .

18) .

19) .

20) .

21) .

22) .

23) .

24) .

25) .

26) .

 

5.2. Завдання:

 

Звести до ДНФ таке висловлювання.

  Розв‘язок: F=

Побудова досконалої диз'юнктивної нормальної форми (ДДНФ)

 

Теоретичні відомості

 

Визначення. Нехай – деяка множина логічних змінних. Елементарна кон’юнкція, в яку входять усі логічні змінні, називається повною елементарною кон’юнкцією щодо множини .

Визначення. Нехай є повною елементарною кон’юн­к­­цією щодо множини . Тоді  містить у таблиці істинності лише одну одиницю, причому на наборі . І навпаки, якщо в таблиці істинності висловлення  є лише одна одиниця на наборі , то  є повною елементарною кон’юнкцією, причому

Визначення. Нехай – висловлення. Позначимо через  множину всіх наборів , на яких .  називається множиною істинності висловлення . Можна записати, що .

Теорема. Якщо , то .

Визначення. Диз'юнктивна нормальна форма називається досконалою (ДДНФ), якщо всі складові її елементарної кон’юнкції є повними.

Теорема. Нехай – висловлення, що не є тотожно хибним, тобто ,тоді

 

6.2.Завдання:

 Звести до ДНФ таке висловлювання. ;

Розв‘язок:

 

X	Y	Z	W
0	0	0	0	1	1	1	0	0	1	1	1
0	0	0	1	1	1	1	1	1	0	0	0
0	0	1	1	0	0	0	1	1	0	1	0
0	1	1	1	0	0	0	1	1	0	1	0
1	1	1	0	0	1	1	1	1	0	0	0
1	1	0	0	0	1	1	1	1	0	0	0
1	0	0	0	1	1	1	0	1	0	0	1
1	1	1	1	0	1	1	1	1	0	0	0

 

X	Y	Z	W
0	0	0	0	1	0	1	1
0	0	0	1	1	0	0	0
0	0	1	1	0	1	1	1
0	1	1	1	0	0	1	1
1	1	1	0	1	1	1	1
1	1	0	0	1	1	0	1
1	0	0	0	1	0	1	1
1	1	1	1	1	1	1	1

Графи

Теоретичні відомості