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

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	f₀	f₁	f₂	f₃	f₄	f₅	f₆	f₇	f₈	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄	f₁₅
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	f₁	f₂	f₃	f₄	f₅	f₆	f₇	f₈	f₉	f₁₀
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. Докажите, что любая натуральная степень полинома Жегалкина равна исходному полиному.

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