Спирина, М.С. Дискретная математика

Т а б л и ц а 4.20 Таблица истинности функции F *1 *2 *3 F (x ,, х2, х3) 0 0 0 F ( 0, 0, 0) = 0 0 0v0 0 0 = 0v0 = 0 0 0 1 F ( 0 , 0, 1) = 0 0 • 1 v 0 • 0 ■Т = 0 v 0 = 0 0 1 0 F ( 0 , 1, 0) = 0 • Т - 0 v 0 • 1 0 = 0 v 0 = 0 0 1 1 F ( 0, 1, l) = 0 T l v 0 l T = 0v 0 = 0 1 0 0 F( l , 0, 0) = l ■ 0 • 0 v 1 • 0 • 0 = 0 v 0 = 0 1 0 1 F ( 1, 0, 1) = 1 ■ 0 1v 1 0 T= 1v 0= 1 1 1 0 /’ (l, 1, 0) = 1 T- 0 v 1 • 1 • 0 = 0 v 1 = 1 1 1 1 F ( 1, 1, l ) = l l l v l l l = 0 v 0 = 0 Задача 21. Пусть при п = 3 булева функция задана таблицей истинности (табл. 4.21). Составить СДНФ и СКНФ для данной функции. Решение. Каждому набору переменных (строке) поставим в со­ ответствие элементарную конъюнкцию, причем каждому аргументу хк = 1_будет соответствовать хк, а каждому хк = 0 будет соответство­ вать хк в соответствующей элементарной конъюнкции. Составим булеву функцию, объединив дизъюнкцией те эле­ ментарные конъюнкции, которые дают значение соответствующего булевавыражения, равное единице: F(xu х2, х3) = ~хх {х2 v xjx2x3 v v Х[Х2х 3. В результате получили СДНФ. Это правило справедливо для любой булевой функции. Чтобы построить СКНФ для некоторой функции F, надо по­ строить F b СДНФ, т.е. взять дизъюнкцию элементарных конъюн- Т а б л и ц а 4.21 Таблица истинности булевой функции трех переменных *2 *3 F(x i, x2, x3) Элементарные конъюнкции 0 0 0 0 *i • *2 • *3 0 0 1 0 Xi- x2 - x3 0 1 0 1 xi • x2 • x3 0 1 1 1 Xi • x2 ■ x3 1 0 0 0 *1 *2 • Xj 1 0 1 0 Xl ■ x2 • X3 1 1 0 1 X[ •X2 • X3 1 1 1 0 JCl • X2 • *3 174