а) ((А В) (С A)) (B C);
б) ((((А В) A) B) C) С;
а) (А (В С)) ((А C) (А B)).
2. Довежда се до PDNF и SKNF формула:
3. В даден набор от променливи, които да изградят елементарни връзка, вярно само за този набор от променливи.
4. В даден набор от променливи, които да изградят една елементарна дизюнкция фалшива само за този набор от променливи.
5. Изграждане SKNF и PDNF еквивалентна на тази формула, и е установено, интерпретация, в която формула е вярно или невярно:
6. За G и Н функции, определени в Таблица 1, за да намерите SKN - и VOS - форма и проста формула, която изпълнява тези функции.
7. Създаване на два булеви функции, които планират 1-битов двоичен ехидна според таблицата по-долу
където x1 и x2 - със същото име се нарежда 1 и 2 условия; е1 - прехвърляне единица от LSB; Е2 - количество трансфер единица в MSB; - сумиране резултат.
8. Изграждане на формула на три променливи, което е вярно, ако и само ако точно две променливи са фалшиви.
9. Конструкт формула на трите променливи, които се същата стойност като част (миноритарни) променливи.
10. SKNF формула U изграждане:
а) PDNF двойна формула U *;
б) SKNF U формула;
в) PDNF U формула.
11. PDNF формула U и В строителство PDNF формула:
а) SKNF и PDNF формула (U В);
б) SKNF и PDNF формула (U В);
в) SKNF и PDNF формула (U В).
3. Пълно операции системи
операции система, наречена пълна. ако има някаква логическа операция може да бъде представен чрез формулата по-горе .
Тъй като всеки формула може да бъде представена чрез горната формула, системата 0 => - пълно.
система се свежда до *. определен *. Ако всички операции система * може да бъде представена от формулите по-горе система. * Ако пълен, след пълна.
Последното твърдение дава един начин да се докаже, пълнотата на дейността на системата - намаляването му до известна цялостна система, като 0. Това е пълна, ще система чрез действието, на които може да се изрази като връзка, дизюнкция и отрицание.
Задача. Докажете, пълнотата на 5 = системата.
Решение. 5 намаляваме система за цялостна система 0.
.
Ако произволна формула Zhegalkin алгебра, осъзнавайки, булева функция е, отворете скобите и да направи всички възможни опростявания, получаваме формула е представена под формата на сума от продукти, която е полином от мод 2. Тази формула се нарича полином Zhegalkin за тази функция. Тя се нарича линейна функция, която е линеен полином Zhegalkin.
Задача. Настояща формула (х1 х2) (
(X1 х2) (
= X1 x2 x3 x1
Получената полином не е линеен и има степен на три.
Да бъдат сведени до пълна експлоатация, системата е необходимо условие за пълнотата на системните операции. Необходимо и достатъчно условие за пълнота на операциите на системата се формулира по отношение на булеви функции.
Системата на булеви функции F се нарича пълна, ако всяка функция може да се прилага по формулата F.
теорема публикация. Булева система от функции е пълна, ако и само ако той съдържа най-малко една функция, не спести 0, най-малко една функция, не спести 1, най-малко един nesamodvoystvennuyu функция, поне един не-монотонна функция и най-малко един нелинеен функция.
Задача. 0 докаже пълнотата на системата. използвайки необходимо и достатъчно условие за пълнота.
Решение. Помислете за съответния 0 система F0 = булеви функции
Класът на функции запазване 0.
Класът на функции запазване 1.
Свързани статии