Всюду далее скобки в формулах восстанавливайте самостоятельно.

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 то A^C = B^D ? Приведите пример, показывающий, что равенство A^B = C^D справедливо не всегда.

СДНФ и СКНФ

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) = x²; б) g(x) = (x³ + 4×x – 3) mod 2; в) h(x) = min{f(x), g(x)}; г) k(x, y) = x×g(x)^y;

д) а(x, y) = (x Ù y ® x) + x² – y² (mod 2); е) max{a(x, y), k(x, y)}; ж) x^h(x)×y^{a(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.Запишите в виде полиномов Жегалкина: а) отрицание произвольного полинома Жегалкина; б) дизъюнкцию двух произвольных полиномов Жегалкина; в) x₁ Ú … Ú x_n ; г) ; д) .

8.Сколько полиномов Жегалкина от n переменных

а) обращаются в ноль при нулевых значениях аргументов ?

б) обращаются в единицу при нулевых значениях аргументов ?

в) полилинейны (т.е. линейны по каждому аргументу) ?

г)являются мономами ? А суммой двух мономов ?

д)принимаютзначение 1 при единичных значениях аргументов ?

9.Найдите все полилинейные булевы функции от двух аргументов.

10.Найдите все булевы функции от двух аргументов, обращающиеся в ноль при нулевых значениях аргументов, а также все функции, принимающиезначение 1 при единичных значениях аргументов.

11.Пусть задан полином Жегалкина p(x₁ , … , x_n). Как найти все аннулирующие полиномы Жегалкина q(x₁ , … , x_n), для которых p(x₁ , … , x_n)×q(x₁ , … , x_n) = 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.Докажите, что любая натуральная степень полинома Жегалкина равна исходному полиному.

Логическое следование.