Дискретная математика

6 8 3) если раскрыть скобки по первому дистрибутивному закону, то получится д.н.ф., 4) если сгруппировать полученный результат в скобки, пользуясь вторым дистрибутивным законом, то получится к.н.ф. Имеет место теорема. Теорема 3.12. Для того, чтобы формула А была противоречием, необходимо и достаточно, чтобы равносильная ей д.н.ф. содержала в кадсдом слагаемом хотя бы одну пару множителей, из которых один - некоторая переменная, а второй - отрицание этой переменной. Доказательство. Пусть для А равносильной ей д.н.ф. является форма B,vB2V...vBk(k>l). (3.14) где 5( ( 1 < i < к ) есть элементарное произведение. Дизъюнкция (3.14) будет противоречием тогда и только тогда, когда будет противоречием каждая Bi (Ы i< к). Bi - элементарное произведение и по теореме 3,10 будет противоречием тогда и только тогда, когда содержит хотя бы одну пару множителей, из которых один - некоторая переменная, а второй - отрицание этой переменной. Теорема доказана. Следствие 3.1. Формула А будет выполнимой, если равносильная ей д.н.ф. содержит хотя бы одно слагаемое, в котором нет таких множителей, что один из них - некоторая пере.менная, а другой множитель - отрицание этой переменной. Также просто доказать следующую теорему. Теорема 3.13. Для того, чтобы формула А была тавтологией, необходимо и достаточно, чтобы равносильная ей к.н.ф. содержала в каждом множителе хотя бы одну переменную вместе с отрицанием этой же переменной. § 10. Представление произвольной булевой функции в виде формул Известно, что булеву функцию можно задавать табличным и графическим способами, словесным описанием, порождающей процедурой или а аналитическом виде, т.е. в виде формул, Спрашивается, всегда ли можно для булевой функции f (x,,x2,...,x,J найти такую формулу, чтобы значения функции и формулы совпадали при одинаковых значениях переменных, т.е. можно лип р е д с т а в и т ь п о с р е д с т в о м формулы.