Построение таблиц истинности и логических функций

 Построение таблиц истинности и логических функций

 

Логическая  функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

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

Порядок выполнения логических операций в сложном  логическом выражении:

- инверсия;

- конъюнкция;

- дизъюнкция;

- импликация;

- эквивалентность.

Для изменения  указанного порядка выполнения операций используются скобки.

Алгоритм построения таблиц истинности для сложных выражений:

Определить  количество строк:

количество  строк = 2n + строка для заголовка,

n - количество  простых высказываний.

Определить количество столбцов:

- количество столбцов = количество переменных + количество логических операций;

- определить количество переменных (простых выражений);

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

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

Пример: Составить таблицу истинности логического выражения:

D = ¬  А & (B Ú C).

Решение: Ù 

1) Определить количество строк:

на входе  три простых высказывания: А, В, С поэтому n=3 и количество строк = 23 +1 = 9.

2) Определить количество столбцов:

простые выражения (переменные): А, В, С;

промежуточные результаты (логические операции):

¬ А - инверсия (обозначим через E);

B Ú  C - операция дизъюнкции (обозначим через F);

а также искомое  окончательное значение арифметического  выражения:

D = ¬  А & (B Ú C). т.е. D = E & F - это операция конъюнкции.

3) Заполнить столбцы с учетом таблиц истинности логических операций.

А	В	С	Е	F	E& F
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	0	1	0
1	1	1	0	1	0

 

Построение  логической функции по ее таблице  истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z(X,Y):

 

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

 

Составить логическую функцию для заданной таблицы  истинности.

 

Правила построения логической функции по ее таблице истинности:

 

1) Выделить в таблице истинности те строки, в которых значение функции равно.

 

2) Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.

3) Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.

4) Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.

Решение:

1) В первой и третьей строках таблицы истинности значение функции равно 1.

2) Так как строки две, получаем дизъюнкцию двух элементов: ( ) V ( ).

3) Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y: (X & Y) V (X & Y).

4) Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию: Z (X, Y) =(¬ X & ¬Y) V (X & ¬Y).