Построение таблиц истинности

Построение таблиц истинности

Алгоритм построения таблицы истинности

  1. Определить число переменных

  2. Определить число строк в таблице истинности

  3. Записать все возможные значения переменных

  4. Определить количество логических операций и их порядок

  5. Записать логические операции в таблицу исинности и определить для каждой значение

 

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

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0),   (0,1),   (1,0),   (1,1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь:

(0,0,0),   (0,0,1),   (0,1,0),   (0,1,1),

(1,0,0),   (1,0,1),   (1,1,0),   (1,1,1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

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

  

Примеры.

1. Составим таблицу истинности для формулы  , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:

   

Переменные

Промежуточные логические формулы

Формула

0

0

1

0

0

1

1

1

0

1

1

1

1

0

1

1

1

0

0

0

1

0

0

1

1

1

0

0

1

0

0

1

 

 

 

Из таблицы видно, что при всех наборах значений переменных x и y формула  принимает значение 1, то есть является тождественно истинной.

 

 

 

2. Таблица истинности для формулы :

Переменные

Промежуточные логические формулы

Формула

0

0

0

1

1

0

0

0

1

1

0

0

0

0

1

0

1

0

1

1

0

1

1

1

0

0

0

0

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

 

 

 

3. Таблица истинности для формулы :

Переменные

Промежуточные логические формулы

Формула

0

0

0

1

1

0

1

0

0

0

0

1

1

1

0

1

1

1

0

1

0

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

1

0

0

1

1

0

0

0

0

1

0

1

1

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

0

1

0

0

0

0

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.

Comments