Всюду далее скобки в формулах восстанавливайте самостоятельно.
1.Вычислите значения формул при указанных интерпретациях:
а)a ® b ® b ® a при a = b = 0 и при a = 1 , b = 0;
б)a ® (b ® b) ® a при a = b = 0 и при a = 1 , b = 0;
в)((aÚ ) Ù (b ® c)) при a = b = c = 0 и при a = 1 , b = 1, с = 0;
г)a Ú Ù b ® c при a = b = c = 0 и при a = 1 , b = 1, с = 0;
д)a Ù bÚ a ® ® c « a Ú c при a = b = c = 0 и при a = 1, b = 0, c = 0;
е)(((a Ù b)Ú a)®(( ® c) « (a Ú c))) при a = b = c = 0 и при a = 1, b = 0, c = 0;
ж) при a = b = c = 0 и при a = 1, b = 0, c = 0.
2.Для каждой из следующих формул укажите, достаточно ли приведённых сведений для определения значения формулы. Если достаточно, вычислите это значение. Если недостаточно, то покажите, что формула может принимать как значения 1 и 0:
а) ® a, б) (a ® b) ® c, c = 1; в)
«
Ù
, b = 1; г) x Ú (y ® z), y = 1; д) x Ú (y ® z), z = 1; е) p Ù (q ® r) ® (p Ù q), r = 0; ж) x ®
, y = 0 = z.
3.Постройте таблицы истинности формул задания 1. Классифицируйте полученные формулы.
4.Дайте классификацию следующих формул, используя таблицы истинности:
а) , б)x ® (y ® x), в)(a®
) ® (b ® c) Ù
Ù
,г)
, д)(a ® (b ® c)) ® ((a ® b) ® (a ® c)), е)(p ® q) Ù (q ®
) Ù (r ® p), ж)a ® a Ú b, з)(x ® y) ® ((x ® (y ® z)) ® (x ® z)), и)x ® y ® x, к)
, л)x ® y Ù (x ® y), м) ((a ® b) ® ((a ® c) ® (a ® b Ù c))), н)(x ® z) ® ((y ® z) ® (x Ú y ® z)).
5.Докажите теорему об основных законах логики, построив таблицы истинности (см. приложение 1).
6.Не строя таблиц истинности, выясните, являются ли следующие формулы законами логики или противоречиями:
а) , б)x « (
® x), в)
, г)u « (u ®
), д)a Ú (a «
),
е)(x Ú x) ® (x Ù x), ж) , з)(p ® q) Ú (q ® p).
7.Докажите, что если формулы A и A ® B являются законами логики, то B – тоже закон логики. Приведите пример таких тождественно истинных формул B и A ® B, для которых A – не тождественно истинна.
8.Верны ли следующие утверждения ?
а) если A Ú B и Ú С – законы логики, то B Ú C – закон логики;
б) если A Ú B, A ® C и B ® D – законы логики, то C Ú D – закон логики;
в)если A Ú B и Ú С – законы логики, то B Ù C – закон логики;
г) если Ú B и
Ú
– законы логики, то A ®
Ú
– закон логики;
д) если A ® B и B ® являются законами логики, то B – закон логики;
е)если A « B и B ® C – законы логики, то A ® C – закон логики;
ж) если Ú B и
Ú
– законы логики, то A ®
– закон логики.
9.Докажите, что формула, полученная из переменных и их отрицаний с помощью дизъюнкциине может быть противоречием.
10.Докажите, что формула, полученная из конъюнкций переменных и их отрицаний с помощью дизъюнкциине может быть противоречием (переменная и её отрицание не могут одновременно входить в конъюнкцию).
11.Докажите, что формула, полученная из дизъюнкций переменных и их отрицаний с помощью конъюнкциине может быть тавтологией (переменная и её отрицание не могут одновременно входить в дизъюнкцию).
12.Приведите пример закона логики, в котором, используется только а) импликация, б) эквивалентность. Какова наименьшая длина такой формулы ?
13.Существует ли закон логики, в котором используются только а) конъюнкция, б) дизъюнкция, в) конъюнкция и дизъюнкция.
14.Существует ли противоречие, в котором используется только а) импликация, б) эквивалентность, в) конъюнкция, дизъюнкция и импликация, г) конъюнкция, дизъюнкция и эквивалентность ?
Равносильные формулы ИВ
1.Докажите теорему об основных равносильностях (см. приложение 2).
2.Проверьте равносильность формул с помощью таблиц истинности:
а) x Ú z ® y Ù º
Ù
; б)a Ù
Ú (
® b) º
® (
® a); в) a Ù x ® y º
;г) a Ù (x ® y) º
;д) 0 ®
º
;
е) a « 1 ® 0Ú º a Ú 1; ж)
® 1 Ù
« 0 º
Ù b; з) (a ® 1) Ú (0 Ù 1) º 1.
3.С помощью основных равносильностей приведите равносильные формулы предыдущего задания к одинаковому виду. Докажите неравносильность остальных формул предыдущего задания, предварительно упростив их с помощью равносильных преобразований.
4.Каким условиям должны удовлетворять формулы А и B для того, чтобы выполнялись следующие свойства ?
а) А Ú B º A Ù B, б) A ® B º B ® A, в) A Ù º
Ù B, г) (В ® A) ® (
®
) º 1, д)
º
Ù A, е) А Ù (
Ú
) º В Ù
, ж)
º
Ù A, з) А Ú B º A Ù B, и) (
®
) « (В ® A) º 1.
5.Используя основные равносильности, упростите формулы:
а) ® ((P Ú Q) ® P); б) (x « y) Ù (x Ú y); в) (a ® b) Ù (b ®
) Ù (c ® a); г) p ® q ® p ® q; д)
Ú y ® x « x ®
Ú y ; е)
Ù x Ú y ®
«
Ù y Ú x ® x;
.
6.Приведите формулы предыдущего задания к дизъюнктивной и конъюнктивной формам.
7.Приведите следующие формулы к дизъюнктивной и конъюнктивной формам:
а) ((u ® v) ® (w ® )) ® (
®
); б) (
Ù
« x) Ù (x ® y ) ®
;
в) (p Ú q) Ù Ú p Ù q Ú (
Ù p); г) u ® v ®
®
®
® w ;
д) (u ® (v ® w)) ® ((u ® ) ® u); е) x Ù (y Ú
) Ù (
Ú x) Ú (
Ù y);
ж) (A Ú ® C) ® (A ® B Ù
Ú
); з) (p Ù q ®
) Ù
Ú
Ù q ;
и) u Ù v Ú ® (u Ù v) Ú
®
Ù
; к) (A Ú
Ù C) Ù (A Ú B Ù
Ú
).
8.Запишите следующие формулы, используя только знак отрицания и логические связки а) Ù, Ú , б) Ù, ® , в) Ú , ® : 1) ((x Ú ® z) ® (z Ù x « y)) Ù (
Ù
Ú
), 2)x Ù y Ú y Ù z Ú x Ù z, 3)
Ù
Ù
Ù
Ú
Ù
, 4) x Ú y Ù y Ú z Ù x Ú z, 5) (
Ú
®
Ú
) «
Ú
.
9.Можно ли формулу Ú
записать, используя только связки Ù , Ú , но не используя отрицания ? А с помощью Ú и ® , но не используя отрицания ? А используя связки Ù , Ú и ® , но не используя отрицания ?
10.Докажите, что заменив любую подформулу в формуле ИВ на равносильную ей, получим формулу, равносильную исходной.
11.Верно ли, что если A º B и С º D то AC = BD ? Приведите пример, показывающий, что равенство AB = CD справедливо не всегда.
СДНФ и СКНФ
1.Постройте СДНФ и СКНФ формул: а) (a ® b) Ù « bÚ a ;б) a ®
;в) (x Ú (
Ù y)) « (x Ú y) ;г)
;е) x ®
Ú r « s ® x ; ж) (a ® (b ® c)) ® ((a ® b) ® (a ® c)) ; з)
; и) (p ® q) Ù (q ®
) Ù (r ® p) ;к)a ® a Ú b ; л)(x ® y) ® ((x ® (y ® z)) ® (x ® z)) ; м)x ® y ® x ; н)x ® y Ù (x ® y) ; о) ((a ® b) ® ((a ® c) ® (a ® b Ù c))) ; п) (x ® z) ® ((y ® z) ® (x Ú y ® z)) ; р)
.
2.Приведите формулы задания 1 к СДНФ и СКНФ с помощью равносильных преобразований формул.
3.Приводя формулы к СДНФ или СКНФ, проверьте равносильность формул:
а) (x ® y) º ;б)
º (x Ù
) Ú (
Ù z) ;в) (x ® y Ù
) º
;г) x Ú y ®
º
Ú y ; д)
º (x Ù
) Ú (
Ù y) ; е) x ®
º
Ú y ; ж)
® 1 Ù
« 0 º
Ù b ; з) a Ù y ® x º
;и) 0 ®
º
.
4.Классифицируйте формулы, приведя их к СДНФ или СКНФ :а) ;б) a Ú b Ù (
Ú c ® b) ® c ® b;в) a ®
Ù c Ú b «
;г) u Ú (v Ù w) ® w Ù u ; д) a Ú
«
Ù b ®
; е)
;ж) v ® (w Ú u) Ù v ;з) a «
® b Ú c ; и) p ® u Ú
«
Ù v ® p Ú
.
5.Постройте формулу от трёх переменных, которая истинна тогда и только тогда, когда ровно две из этих переменных ложны.
6.Постройте формулу от трёх переменных, которая принимает такое же значение, как и большинство её переменных.
7.Найдите такую формулу X, что
а) ((X Ù y) ® ) ® ((z ®
) ® X) – закон логики;
б) ((r ® ( Ù p)) ® X) ® (X Ù (p ® q)Ù r) – закон логики;
в) ((X Ù y) ® ) ® ((z ®
) ® X) – противоречие;
г) ((r ® ( Ù p)) ® X) ® (X Ù (p ® q)Ù r) – противоречие;
в) X ® (p Ú q Ù ) º p ® (q Ú r Ù
);
г) u Ú X Ù v Ú X º X ® u Ù X ® v.
8.Почему импликация не выражается через конъюнкции и дизъюнкции без использования отрицания ? Можно ли выразить эквивалентность через импликацию и дизъюнкцию ?
9.Докажите, что если дизъюнкция конъюнкцийтождественно ложна, то в каждой конъюнкции некоторая переменная участвует вместе со своим отрицанием.
10.Докажите, что если конъюнкция дизъюнкцийтождественно истинна, то в каждой дизъюнкции некоторая переменная участвует вместе со своим отрицанием.
11.Докажите, что формула, записанная только с помощью связки « , является законом логики тогда и только тогда, когда каждая переменная в ней участвует чётное число раз.
12.Докажите, что формула, записанная только с помощью связок « и , является законом логики тогда и только тогда, когда каждая переменная в ней и связка
участвует чётное число раз.
13.Докажите, что равносильные СКНФ отличаются только порядком своих совершенных элементарных дизъюнкций.
14.Постройте наиболее простые РКС по функциям проводимости:
а) (a ® b) Ú (b ® a);б) x Ú ( Ù y) ® (x Ú y);в) (x Ú y Ú z) Ù (x Ù
« x Ù
);
г) (((x Ù ®
) ®
) Ú
Ù z) Ù y ; д) (a « b) Ú (
) Ù a ® b ; е)
® y ; ж) (p Ú q) Ù
Ú p Ù q Ú (
Ù p) ; з) (p Ù q ®
) Ù
Ú
Ù q ; и) a Ù b « a Ú b .
15.
![]() |
УпроститеРКС:
16.Проверьте равносильность РКС:
17.Постройте РКС
а) с четырьмя переключателями, зажигающую лампочку, если, и только если, включены ровно два из них;
б)с четырьмя переключателями, зажигающую лампочку, если включено два или три из них;
в) с четырьмя переключателями, зажигающую лампочку тогда и только тогда, когда включены переключатели с чётными номерами, но выключены переключатели с нечётными номерами.
18.Пусть S(x, y, T) = (x Ù y Ù ) Ú (x Ù
Ù T) Ú (
Ù
Ù T) Ú (x Ù y ÙT),
R(x, y, T) = (x Ù Ù
)Ú (
Ù y Ù
) Ú (
Ù
Ù T) Ú (x Ù y ÙT).
Докажите, что S(x, y, T) º (x Ù y) Ú (x Ù T) Ú (y Ù T),
R(x, y, T) º (x Ù y Ù T) Ú Ù (x Ú y Ú T),
и постройте интегральную схему с тремя входами x , y , T и двумя выходами R , S .
Булевы функции
1.Задайте табличным способом следующие булевы функции:
а) f(x) = x2; б) g(x) = (x3 + 4×x – 3) mod 2; в) h(x) = min{f(x), g(x)}; г) k(x, y) = x×g(x)y;
д) а(x, y) = (x Ù y ® x) + x2 – y2 (mod 2); е) max{a(x, y), k(x, y)}; ж) xh(x)×ya(x, y).
2.Задайте табличным способом следующие булевы функции:
.
3.Задайте формулами следующие булевы функции: а) формулами ИВ, б) полиномами Жегалкина, в) другими формулами на Ваш вкус.
x | y | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 |
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 |
x | y | z | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 |
0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
4.Следующие формулы запишите в виде полиномов Жегалкина:
а); б) x Ù y ®
;в)
; г)xÙ
Ú
Ù y; д)a ®
Ù c Ú b «
; е)
; ж) p Ù (q ® r) ® (p Ù q); з) x ®
;и)
; к) x ® y Ú z; л)
; м)
; н) a ® (b ® b) ® a; о)
Ù x Ú y ®
«
Ù y Ú x ® x .
5.Для следующих полиномов Жегалкина найдите СДНФ и СКНФ:
а) a + b + 1; б) u×v + u; в) a×b + b + a + 1; г) x×y×z + x×z +y; д) x×z + y×z + x×y; е) x×y×z×p + x×z + 1; ж) x×y×z×p + x×y + y×p + x×z + 1; з) x×(y + z) + y×(x + z) + 1.
6.Запишите в виде полиномов Жегалкина булевы функции заданий 1, 2.
7.Запишите в виде полиномов Жегалкина: а) отрицание произвольного полинома Жегалкина; б) дизъюнкцию двух произвольных полиномов Жегалкина; в) x1 Ú … Ú xn ; г) ; д)
.
8.Сколько полиномов Жегалкина от n переменных
а) обращаются в ноль при нулевых значениях аргументов ?
б) обращаются в единицу при нулевых значениях аргументов ?
в) полилинейны (т.е. линейны по каждому аргументу) ?
г)являются мономами ? А суммой двух мономов ?
д)принимаютзначение 1 при единичных значениях аргументов ?
9.Найдите все полилинейные булевы функции от двух аргументов.
10.Найдите все булевы функции от двух аргументов, обращающиеся в ноль при нулевых значениях аргументов, а также все функции, принимающиезначение 1 при единичных значениях аргументов.
11.Пусть задан полином Жегалкина p(x1 , … , xn). Как найти все аннулирующие полиномы Жегалкина q(x1 , … , xn), для которых p(x1 , … , xn)×q(x1 , … , xn) = 0 ? Найдите все аннулирующие полиномы для
а) p(x) = x, б) p(x) = 1+x,б) p(x, y) = x+y, в) p(x, y) = x+x×y, г) p(x, y) = 1+x+y+x×y, д) p(x, y, z) = x + y + x×z, е) p(x, y, z) = x + z + x×z, ж) p(x, y, z) = 1+ x + y×z.
12.Докажите, что любая натуральная степень полинома Жегалкина равна исходному полиному.
Логическое следование.