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

таблицы, которую называют т аблиц ей и сти нн о сти . В данном случае она примет вид (табл. 4.2). Б ул евы ф ункции д в у х п ер ем ен ны х . При п = 2 существуют 16 булевых функций. Их виды приведены в табл. 4.3. Приведенные в табл. 4.3 функции можно разделить на три кате­ гории. 1. С имм етри ч ески е ф ункции . Ф ункци я^ = (0001), которая равна 1 , только если оба аргумента равны 1 , называется к онъю нкци ей (от лат. conjungere — объединять) и обозначается как / (х , у) = х л у или х & у. Однако чаще употребляется / (х , у) = х •у = ху. В дальней­ шем будем пользоваться именно последними обозначениями. Иног­ да удобно представление ху - min(x, у). Функция / 8 = (0111), значение которой равно 0, только если оба аргумента равны 0 , называется д и зъ ю н к ц и е й (от лат. disjunc- tio — разделять). Обозначается как / (х , у) - х v у. Иногда удобно представление ху = шах (х, у). Функция / 10 = (1001), равная 1 только при совпадающих аргу­ ментах, называется эк в и в ал ен ц и ей (от лат. aequivalens — равно­ значный). Обозначается к ак / (х , у) = (х = у). Также может исполь­ зоваться знак - . Функция f 7 = (ОНО), равная 0 только при совпадающих аргу­ ментах, называется с у м м о й п о м о д у лю д в а . Обозначается как / (х , у) = х ® у. Также применяются знаки + и V . Другое название — строгая дизъюнкция: значение функции равно 1 , если либо пер­ вый, либо второй аргументы равны 1 , но никак не оба одновре­ менно. Следуя традиции, будем употреблять термин сумма по мо­ дулю два и знак ®, когда речь идет только о булевых функциях, и термин строгая дизъюнкция и знак V для высказываний, когда надо определить именно истинность, хотя фактически это одно и то же. Очевидно, что эта функция является отрицанием эквива- ленции: V(x, у) е В2 х ® у = х =у. Функция f 9 = (1000), равная 1, только если оба аргумента рав­ ны 0, называется с тр ел к о й П и р с а . Обозначается к ак / (х , у) = х I у. Стрелка Пирса является отрицанием дизъюнкции. Т а б л и ц а 4.3 Таблица истинности булевых функций двух переменных *1 *2 / . 0 /2 А /з и Xl /5 /б Х2 /7 0 А V А 1 /ю /и Х2 /l2 /13 Xl / и /и 1 /|6 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 137