Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

§3. Равносильность и законы логики высказываний

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

§6. Контактные схемы.

Задачи

1. Определить, какая логическая связка используется в следующих выражениях: "А, если В", "коль скоро А, то В", "в случае А имеет место В", "как А, так и В", "для А необходимо В", "для А достаточно В", "А вместе с В", "А не имеет места", «A, только если B», «A, пока B», «или A, или B», «A одновременно с B», «A – то же самое, что и B».


2. Записать следующие рассуждения в виде последовательности формул логики высказываний.

2.1. Профсоюзы штата будут поддерживать губернатора, если он подпишет этот закон. Фермеры окажут ему поддержку, если он наложит на него вето. Очевидно, что он или не подпишет закон, или не наложит на него вето. Следовательно, губернатор потеряет голоса рабочих, объединенных в профсоюзы, или голоса фермеров.

2.2. Если мы не будем продолжать политику сохранения цен, то мы потеряем голоса фермеров. Если же мы будем продолжать эту политику и не прибегнем к контролю над производством, то продолжится перепроизводство. Без голосов фермеров нас не переизберут. Значит, если нас переизберут, и мы не прибегнем к контролю над производством, то продолжится перепроизводство.

2.3. Если завтра будет хорошая погода, то я буду кататься на коньках или я пойду на лыжах. Если я пойду на лыжах, то лучше поехать за город, а если буду кататься на коньках, то останусь в городе. Мне не хочется завтра в выходной день оставаться в городе. Следовательно, если завтра будет хорошая погода, то я пойду на лыжах.


3. Будут ли следующие формулы тождественно истинны:

а) X & Y ® X, б) X Ú Y ® Х, в) X & Y ® Х Ú Y ,
г) X Ú Y ® X & Y, д) (Х®Y)®(Y®Х), е) (Х®ØX)®X,
ж) (ØX®X)®X , з) (X®Y)®(ØY®ØX), и) Ø(X«Y)®(ØX«ØY)?

4. Существует ли формула F такая, что формула G тождественно истинна:

а) G = X & Y ® Ø F & Z; б) G = (F & Y®ØZ) ®( Z®ØY);
в) G = (F & Y ®ØZ) ® (( Z®ØY)® F ) ?  

5. Будут ли следующие формулы равносильны:

а) Х ® Y и ØY ®ØX, б) ØX ®Y и ØY ® Х
в) Х® (Y®Z) и (Х®Y) ®Z, г) Х ® (Y ® Z) и X & Y® Z,
д) Ø(X ® Y ) и ØX ®ØY, е) X«Y и ØX«ØY?

6. Доказать равносильность формул:

а) Ø[(XÚY)&(X&ØZ)] и X®Z, б) (X&ØY)ÚØ(X&Y) и Ø(X&Y)
в) Ø[(XÚØY)&Y]&Ø(ØX&Y) и ØY г) Ø [(X & Y) Ú ØZ] и Ø (Z®X) Ú Ø(Z®Y),
д) (X & Y) Ú (ØX & Y) Ú (X & ØY) и Х Ú Y,
е) (ØX & Y & Z) Ú (ØX & ØY & Z) Ú (Y & Z) и (ØXÚY)&Z.

7. Доказать, что формула G является логическим следствием формул F1,F2,...,Fn:

а) F1=X ® Y Ú Z, F2=Z®W, F3=ØW, G=X®Y;
б) F1=XÚYÚØZ, F2=X®X1, F3=Y®Y1, F4=Z, G=X1ÚY1;
в) F1=X®Y&Z, F2=Y®Z1ÚZ2, F3=Z®Z1, F4=ØZ1, G=X®Z2;
г) F1=Z®Z1, F2=Z1®Y, F3=X®YÚZ, G=X®Y.

8. Доказать, что формула G не является логическим следствием формул F1,F2,...,Fn:

а) F1=XØYÚZ, F2=Y®W, F3=Z®X, G=X ® W;
б) F1=X®Y, F2=Y®Z, F3=Z®Z1ÚZ2, G=X®Z1;
в) F1=XÚYÚZ, F2=X®X1, F3=Y®Х1ÚY1, F4=ØY1, G=Z®X1.

9. Будет ли логичным рассуждение из задач 2.1, 2.2, 2.3 ?


10. Будет ли логичным следующее рассуждение ?

10.1. Если Джонс не встречал этой ночью Смита, то Смит был убийцей или Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство произошло после полуночи. Если убийство произошло после полуночи, то Смит был убийцей или Джонс лжет. Эксперты установили, что убийство произошло до полуночи. Следовательно, Смит был убийцей.


10.2. В бюджете возникнет дефицит, если не повысят пошлины. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят пошлины, то расходы на социальные нужды не сократятся.


10.3. Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.


10.4. Если губернатор не имеет соответствующего авторитета или если он не желает принимать на себя ответственность, то порядок не будет восстановлен и волнения не прекратятся до тех пор, пока участникам волнений это не надоест, и власти не начнут примирительные действия. Следовательно, если губернатор не желает взять на себя ответственность и участникам волнений это не надоест, то волнения не прекратятся.


11. Привести формулы к ДНФ:

а) (Х®Y) & (Y®Х); б) Ø[(X®Y) & (Y®Х)],
в) Ø(XÚZ) & (X®Y); г) Ø(X & Y ® Х).

12. Привести формулы к СДНФ:

а) ХÚ(Y&Z); б) (Х®Y) & (Y®Х);
в) Ø(XÚY) & (X®Z); г) X&Y ® Ø (XÚY).

13. Привести формулы к КНФ:

а) (Х®Y) & (Y®Х); б) Ø[(X®Y) & (Y ® Х)];
в) XÚY ® X&Y; г) Ø(X&Y ® ХÚZ).

14. Для следующих схем построить эквивалентные им более простые цепи:

а)


б)


в)


15. Требуется, чтобы включение света в комнате осуществлялось с помощью трех различных выключателей таким образом, чтобы нажатие на любой из них приводило к включению света, если он был выключен, и выключению, если он был включен. Построить по возможности более простую цепь, удовлетворяющую этому требованию.

16. Пусть каждый из трех членов комитета голосуют "за", нажимая кнопку . Построить по возможности более простую цепь, которая была бы замкнута тогда и только тогда, когда не менее двух членов комитета голосуют "за".

Ответы, указания и решения

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru