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

 

1.      Вычислить количество строк и столбцов таблицы истинности.

Пусть сложное высказывание состоит из n простых.

Количество строк: 2ⁿ +2 (2-строки заголовка).

Количество столбцов: сумма количества переменных (n) + количества логических операций, входящих в сложное высказывание.

 

2.      Начертить таблицу и заполнить заголовок.

Первая строка – номера столбцов.

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

 

3.      Заполнить первые n  столбцов.

Для n=3 количество строк со значениями переменных равно 8.

8:2=4: в 1-м столбце чередуем 4 нуля и 4 единицы.

4:2=2: во 2-м столбце чередуем 2 нуля и 2 единицы.

2:2=1: в 3-м столбце чередуем 1 ноль и 1 единицу.

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

 

4.      Заполнить остальные столбцы.

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

19. Логические законы и правила преобразований.

Законы логики отражают наиболее важные закономерности логического мышления. В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений.  Закон тождества. Всякое высказывание тождественно самому себе:  А = А  Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:  А&!А = 0  Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение "истина"  Аv!А = 1  Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:  !!А = А  Законы де Моргана.  !(А v В) = !А &!В !(А & В) = !А v !B  Важное значение для выполнения преобразований логических выражений имеют законы алгебраических преобразований. Многие из них имеют аналоги в обычной алгебре.Закон коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:  Логическое умножение Логическое сложение  А &В =В &А Аv В =А vВ

Логическое умножение	Логическое сложение
А &В =В &А	Аv В =А vВ

Закон ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебре­гать скобками или произвольно их расставлять:

Логическое умножение	Логическое сложение
(А & В) & С = А & (В & С)	(А v В)v С=Аv(В v С)

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

Для дизъюнкции:	Для конъюнкции:
Аv1=1 Аv0=А.	А&1=А А&0=0.

Закон идемпотентности. Закон означает отсутствие показателей степени. 

Для дизъюнкции:	Для конъюнкции:
АvА=А.	А&А=А

Закон поглощения:

Для дизъюнкции:	Для конъюнкции:
Аv(А&В)=А	А&(АvВ)=А

Закон исключения:

Для дизъюнкции:	Для конъюнкции:
(А&В)v(!А&В)=В	(АvВ)&(!АvВ)=В

Раскрытие импликации:

А->В=!АvВ

!(А->В)=А!&В