3.6 Вопросы для самопроверки
1. Составьте таблицы истинности для формул:
а)
б)
в)
г)
д)
x |
y |
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
3.2. Установите с помощью таблиц истинности какие из следующих формул - тавтологии:
а)
б)
в)
г)
д)
е)
3. На основании каких законов логики получены следующие соотношения? Докажите их с помощью таблиц истинности :
;
;
;
;
;
;
;
;
;
;
;
;
4. Какие из данных формул равносильны:
а)
б)
в)
г)
д)
е)
ж)
з)
5. Полиция задержала 4 гангстеров, подозреваемых в краже автомобиля: Анри, Луи, Жоржа и Тома. При допросе они дали следующие показания: Анри: «Это был Луи», Луи: «Это сделал Том», Жорж: «Это не я», Том: «Луи лжет, говоря, что это я». Дополнительное расследование показало, что правду сказал только один из них. Кто украл машину?
х |
y |
z |
F1 |
F2 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
6. Составьте формулы, соответствующие данной таблице истинности (выберите рациональный способ). Упростите полученные формулы и изобразите их в виде контактных схем.
7. Для каждой из данных формул найдите ее СДНФ и СКНФ:
а)
б)
в)
г)
8. Напишите СДНФ представляющую: а) тавтологии с переменными х и у; б) тавтологии с переменными х, у и а; в) тождественно ложные формулы с переменными х, у и а.
Пример:
.
9. Составьте всевозможные таблицы истинности для формул с 2 переменными х и у. Выпишите СДНФ и СКНФ формул, соответствующих этим таблицам. Укажите 16 таких таблиц.
10. Один логик попал в плен дикарям в пещеру, имеющую 2 выхода. Вождь дикарей предложил логику следующий шанс на спасение: «Один выход ведет на свободу, другой на смерть. Сделать выбор тебе помогут два моих воина, одному из которых ты можешь задать единственный вопрос. Но предупреждаю тебя, что один из этих воинов всегда говорит правду, а другой всегда лжет». Что должен спросить логик?
11. Установите, какие из данных формул являются ДНФ, СДНФ, УНФ и СКНФ формул с переменными х, у и z:
а)
б)
в)
г)
д)
е)
ж)
Примечание:
Для приведения к СДНФ, если в какой-либо
конъюнкции не содержится переменной я
из числа переменных, входящих в исходную
формулу, надо добавить к этой конъюнкции
член (
)
и применить закон распределительности
конъюнкции относительно дизъюнкции
(для приведения к СКНФ член
соответственно)
.
12. Приведите следующие формулы к СДНФ с помощью равносильных преобразований:
а)
б)
в)
г)
д)
е)
13. Приведите следующие формулы к СКНФ с помощью равносильных преобразований и проверьте их с помощью таблиц истинности :
а)
б)
в)
г)
д)
Примечание:
.
14. Найти все булевы функции от 2х переменных являющиеся:
а) линейными; б) монотонными; в) самодвойственными.
15. Установить является ли самодвойственной функция эквивалентности.
16. Привести пример монотонной функции, которая одновременно была бы линейной.
17. Убедиться, что функции Шеффера и Вебба не являются ни линейными, ни монотонными.