Лекція 2 План

1. Логічні значення складного висловлення.

2. Класифікація формул алгебри висловлень.

3. Тавтології алгебри висловлень.

4. Основні правила одержання тавтологій.

1. Логічні значення складного висловлення.

Зазначимо, що у алгебрі висловлень розглядаються лише логічні значення висловлень, а не їх зміст. Якщо у формулу алгебри висловлень F(X₁, X₂, ..., Х_n) замість пропозиційних змінних X₁, X₂, ..., Х_n підставити конкретні висловлення A₁, A₂, ..., A_n то одержимо деяке нове складне висловлення F(A₁, A₂, ..., A_n). Воно називається конкретизацією формули F(X₁, X₂, ..., Х_n). на наборі висловлень A₁, A₂, ..., A_n.

Якщо формула F(X₁, X₂, ..., Х_n) при підстановці замість її пропозиційних змінних X₁, X₂, ..., Х_n висловлень A₁, A₂, ..., A_n з логічними значеннями λ(A₁)=α₁, λ(A₂)=α₂, …, λ(A_n)=α_n перетворюється у висловлення F(A₁, A₂, ..., A_n) з логічним значенням λ(F(A₁, A₂, ..., A_n))=α, то будемо говорити, що формула F(X₁, X₂, ..., Х_n) приймає значення α, якщо її змінні X₁, X₂, ..., Х_n приймають значення α₁, α₂, …, α_n й відповідно писати X₁=α₁, X₂=α₂, …, X_n=α_n і F(α₁, α₂, …, α_n)=α, где α₁, α₂, …, α_n, α {0, 1}. Для знаходження значення F(α₁, α₂, …, α_n) потрібно підставити у формулу F(X₁, X₂, ..., Х_n) замість пропозиційних змінних X₁, X₂, ..., Х_n значення α₁, α₂, …, α_n і в одержаному виразі послідовно виконати всі дії з нулями й одиницями згідно визначенню відповідних операцій. Для визначення логічного значення формул складаються відповідні таблиці істинності.

Розглянемо приклад. Скласти таблицю істинності для формули .

У перших двох стовпцях таблиці випишемо всі можливі пари логічних значень пропозиційних змінних X і Y. У наступних стовпцях виписуємо логічні значення формул , і , які утворюють так звану породжуючу послідовність для даної формули. В результаті одержимо таблицю

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

Розглянемо ще один приклад. Таблиця істинності формули

має наступний вигляд

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

Таблицю істинності формули можна скласти у скороченому вигляді.

Складемо, наприклад, таблицю істинності для формули . У першому рядку таблиці запишемо дану формулу. Під змінними Х і Y виписуємо всі можливі набори їх логічних значень. Далі стовпець під першим знаком заповнимо логічними значеннями формули , виходячи з відповідних значень змінної Y, а стовпець під знаком  логічними значеннями формули , виходячи з відповідних логічних значень формул і . Потім заповнюємо стовпець під другим знаком значеннями формули і стовпець під знаком  значеннями формули . Нарешті заповнюємо стовпець під знаком логічними значеннями даної формули. В результаті маємо

0 0 1 0 1 1 0

0 0 0 0 1 1 1

1 1 1 0 0 0 0

1 0 0 0 0 1 1.