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

Переменные

Промежуточные операции

Значение выражения

¯¯¯x⋅yx¯⋅y

x⋅¯¯¯yx⋅y¯

¯¯¯x⋅y+x⋅¯¯¯yx¯⋅y+x⋅y¯

⇐ ПредыдущаяСтр 2 из 2

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

Для того, чтобы построить таблицу истинности выражения нужно:

· Определить количество переменных, участвующих в выражении

· Определить количество составляющих выражение логических операций

· Заполнить строки таблицы всеми возможными наборами значений переменных. Наборы значений лучше представлять в виде двоичных чисел. Например, для трех переменных нужно заполнить восемь строк с 000 до 111.

· Вычислить и заполнить промежуточные операции в таблице

· Вычислить и заполнить значение логического выражения

Задача: Построить таблицу истинности для логического выражения ¯¯¯x⋅y+x⋅¯¯¯yx¯⋅y+x⋅y¯

Решение:

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

Строится формула следующим образом:

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

· Для каждой такой строки таблицы строится конъюнкция всех переменных, при этом если значение переменной равно 1, то берется прямое значение переменной, а если равно 0 - инверсное.

· Все полученные конъюнкции объединяются дизъюнкцией

Такая форма записи формулы функции называется дизъюнктивной нормальной формой. В дизъюнктивной нормальной форме присутствуют только основные логические операции (отрицание, конъюнкция, дизъюнкция) и не содержатся отрицания неэлементарных формул.

Дизъюнктивная нормальная форма называется совершенной, если все конъюнкции в ней состоят из одного и того же набора переменных, каждый из которых входит в конъюнкцию один раз.

Задача: Дана полная таблица истинности некоторой функции. Построить формулу функции по этой таблице.

xx	yy	zz	FF
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

1. Удаляем строки со значением функции равным 0

xx	yy	zz	FF
0	1	0	1
1	0	0	1
1	0	1	1
1	1	1	1

2. Составляем конъюнкции для каждой строки

xx	yy	zz	FF	Конъюнкция
0	1	0	1	¯¯¯x⋅y⋅¯¯¯zx¯⋅y⋅z¯
1	0	0	1	x⋅¯¯¯y⋅¯¯¯zx⋅y¯⋅z¯
1	0	1	1	x⋅¯¯¯y⋅zx⋅y¯⋅z
1	1	1	1	x⋅y⋅zx⋅y⋅z

3. Объединяем все конъюнкции дизъюнкцией:

F(x,y,z)=¯¯¯x⋅y⋅¯¯¯z+x⋅¯¯¯y⋅¯¯¯z+x⋅¯¯¯y⋅z+x⋅y⋅zF(x,y,z)=x¯⋅y⋅z¯+x⋅y¯⋅z¯+x⋅y¯⋅z+x⋅y⋅z

Разбор задачи:

Задача: Для какого из указанных XX истинно высказывание ((X>2)→(X>3))((X>2)→(X>3))?

1) 1 2) 2 3) 3 4) 4

Решение:

Введем обозначения (X>2)−A,(X>3)−B(X>2)−A,(X>3)−B, перепишем логическое выражение в удобной нам форме и упростим его, преобразовав импликацию и применив правило де Моргана:

¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯(A→B)=¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯A+B=¯¯¯¯¯¯¯¯A⋅¯¯¯¯B=A⋅¯¯¯¯B(A→B)¯=A¯+B¯=A¯¯⋅B¯=A⋅B¯. Полученное выражение истинно, когда истинны оба множителя, то есть:

{A=1¯¯¯¯B=1{A=1B¯=1 или {X>2X≤3{X>2X≤3 , заметим, что утверждение (X≤3)(X≤3) противоположно утверждению (X>3)(X>3)

Системе неравенств удовлетворяет X=3X=3. Ответ: вариант 3.

Домашнее задание. Решить задачи.

Задача 1: Символом FF обозначено одно из указанных ниже логических выражений от трех аргументов X,Y,ZX,Y,Z. Дан фрагмент истинности выражения FF :

XX	YY	ZZ	FF
1	0	0	1
0	0	0	1
1	1	1	0

Какое выражение соответствует FF? 1) X∧Y∧ZX∧Y∧Z 2) X∧Y∧ZX∧Y∧Z 3) X∨Y∨ZX∨Y∨Z 4) X∨Y∨ZX∨Y∨Z

Задача 2: Укажите, какое логическое выражение равносильно выражению (A ∧ B) ∨ (A ∧ B) ∧ (A ∨ B)?

1) (A ∨ B) ∧ (A ∨ B)

2) A ∧ B

3) A ∧ B

4) A ∧ B ∨ A ∧ B

Ответ на домашнее задание

(в виде фотографий или документов Microsoft Word)

прислать на электронный адрес:
larisanikolaevna.epgl@yandex.ru

Дата добавления: 2020-11-15; просмотров: 204; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!