yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Математическая логика

Упражнения.

1. Определить, являются ли следующие формулы тавтологиями:

а) (xy) ((yz) (xz));

б) (xy) ((zy) xvzy));

в) (x(yz)) ((xy) (xz));

г) (¬x¬y) (xy).

    2. Проверить, являются ли эквивалентными следующие формулы:

а) A(AvB) и AvB;

б) AB и ¬AvB;

в) AB, ¬A¬BvAB и (Av¬B)( ¬AvB)

г)AB и ¬ABv¬BA.

    3. Доказать эквивалентность формул А и В, используя основные аксиомы и теоремы булевой алгебры:

а) A=xyv¬x¬zvx¬z, B=x(¬y¬z)v(¬xv¬z);

б) A=¬x¬y¬zv¬x¬yzv¬xy, B=¬x;

в) A=xyzvxyvz¬z, B=xy;

г) A=x(yvz)vy(¬x¬z)v(¬yvx), B=xvyv¬z.

    4. Представить булевы функции в виде СДНФ, СКНФ и канонического полинома Жегалкина, проверить, являются ли они линейными, монотонными, самодвойственными:

а) xvyvz;

б) (xv¬yvz)( ¬x¬y¬z);

в) ( ¬x¬yv¬y¬z) (xvzy);

г) xyvxzvyz

д) x(xz)

е) (x(xy)) z;

ж)(xy) z.

    5. Проверить полноту систем функций:

а) {xy, xvy, 1};

б) {xyvxzvyz, x};

в) {xy, xvy, 0};

г) {0, 1, (xy) z};

д) {xy, (xy) z};

    6. Найти минимальные ДНФ булевых функций:

а) f(x,y,z,t)=1              на наборах                             0,3,4,7,8,9,11,12;

б) f(x,y,z,t)=1              на наборах                             3,6,8,9,10,13,15;

в) f(x,y,z,t)=1              на наборах                             1,2,4,7,9,10,13,14;

г) f(x,y,z,t)=1              на наборах                             1,3,5,7,8,10,12,14,15;

д) f(x,y,z,t)=1              на наборах                             7,8,9,10,11,12,14,15.

    7. Определить, какие из приведенных формул являются:

1) тавтологиями,

2) противоречиями,

3) нейтральными (знак конъюкции для сокращения записи опущен):

  1. ABvCD (AvB)(CvD)
  2. (A B)(C D) (AvC BvD)
  3. (A (B C)) ((A B) (A C))
  4. (AvB C) (A C)v(B C)
  5. (AB C) ((A C) (B C))
  6. (A B)(C D) (AC BD)

     8. Доказать или опровергнуть:

1.      Если А и В – тавтологии, то А&В – тоже тавтология.

2.      Если А и В – тавтологии, то АvВ – тоже тавтология. Верно ли обратное?

3.      Если А и В – тавтологии, то А В – тоже тавтология.

4.      Если А В – тавтология, то А и В – тавтологии.

    9. С помощью метатеоремы дедукции доказать в теории L:

1.      |−((AB) A) ((AB) B);

2.      |−(AC) (ABvC);

3.      |−(¬AB) (¬BA);

4.      |−((AB) (AC)) (A(BC));

5.      |−(BC) (B(AC));

6.      |−(BA) (AvBA);

7.      |−A&B(CB);

8.      |−(BAvC) ((BC) ((DC) (BvDC)));

9.      |−((BA) C)  (AC).

    10. Построить выводы и доказательства в теории L1:

1.      AB|−CvACvB;

2.      |−(AB) ((CA) (CB))

3.      CA,AB|−CB;

4.      |−AA(т.е. |−¬АvA);

5.      |−Av¬A;

6.      |−A¬¬A;

7.      |−¬B(BC)

8.      |−Av(BvC) ((Bv(AvC))vA)

9.      |−(Bv(AvC))vABv(AvC);

10.  |−Av(BvC) Bv(AvC);

11.  |−(A(BC)) (B(AC));

12.  |−(CA) ((AB) (CB));

13.  |−A(BC), AB|−A(AC);

14.  |−A(BC), AB|−AC;

15.  Г,А|−ВГ|−АВ (метатеорема дедукции);

16.  ВА, ¬ВА|−А.

    11. Построить выводы и доказательства в теории L2:

1.      AB, BC|−¬(¬C&A);

2.      |−¬(¬A&A)

3.      |−¬¬AA

4.      |−¬(A&B) (B¬A)

5.      |−A¬¬A

6.      |−(AB) (¬B¬A)

7.      ¬A¬B|−BA

8.      AB|−C&AB&C

9.      AB, BC, CD|−AD

10.  |−AA

11.  |−A&BB&A

12.  AB,BC|−AC

13.  AB,CD|−A&CB&D

14.  BC|−A&BA&C

15.  |−(A(BC)) ((A&B) C)

16.  |−((A&B) C) (A(BC))

17.  AB,A(BC) |−AC

18.  |−A(BA&B)

19.  |−A(BA)

20.  Г,А|−ВГ|−АВ (метатеорема дедукции)

21.  |−(¬АА) А

22.  АВ, ¬АВ|−В.

12. Проверить логическое следование.

А). Область определения: животные.

1.      Я люблю всех животных, которые принадлежат мне.

2.      Собаки грызут кости.

3.      Ни одно животное я не пускаю к себе в кабинет, если оно не «служит», когда его об этом просят.

4.      Все животные во дворе принадлежат мне.

5.      Всем животным, которых я люблю, разрешается заходить ко мне в кабинет.

6.      Единственные животные, которые «служат» - собаки.

Вывод: Все животные в этом дворе грызут кости.

Б). Область определения: мои мысли.

1.      Любая мысль, которую нельзя выразить в виде силлогизма, поистине смешна.

2.      Моя мечта о сдобных булочках не стоит того, чтобы её записывать на бумаге.

3.      Ни одну мою несбытную мечту нельзя выразить в виде силлогизма.

4.      Мне не приходило в голову ни одной действительно смешной мысли, о которой бы я не сообщил своему поверенному .

5.      Я только и мечтаю, что о сдобных булочках.

6.      Я никогда не высказывал своему поверенному  ни одной мысли, если она не стояла того, чтобы  записать на бумагу.

Вывод: Все мои мечты сбылись.

В). Область определения: предметы

1.      Я с отвращением отношусь ко всему, что не может служить мостом.

2.      Все, что можно воспеть в стихах, для меня приятный подарок.

3.      Радуга не выдержит веса тачки.

4.      Все, что может служить мостом, выдержит вес тачки.

5.      Я не принял бы в качестве подарка то, что вызывает у меня отвращение.

Вывод: Радугу не стоит воспевать в стихах.

Г). Область определения: книги в этой библиотеке.

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

2.      Все книги в твердых переплётах обладают выдающимися литературными достоинствами.

3.      Все романы вполне нравственны по своему содержанию.

4.      Я  не рекомендую читать ни одну из книг в мягкой обложке.

      Вывод: Все романы в этой библиотеке обладают выдающимися литературными достоинствами.

Д). Область определения: вещи.

  1. Все вещи, продаваемые на улице, не имеют особой ценности.
  2. Только дрянь можно купить за грош.
  3. Яйца большой гагарки  представляют большую ценность.
  4. Лишь то, что продаётся на улице, и есть настоящая дрянь.

Вывод: Яйцо большой гагарки за грош не купишь.

Е). Область определения: мальчики учащиеся в этой школе.

  1. Ни одного мальчика моложе 12 лет не принимают в эту школу на полный пансион.
  2. У всех прилежных мальчиков рыжие волосы.
  3. Ни один из мальчиков, приходящих в школу только на занятия, не учит греческий язык.
  4. Никто, кроме мальчиков моложе 12 лет, не любит бить баклуши.

Вывод: Никто, кроме рыжих мальчиков не изучает в этой школе греческий язык.

 

 

 

44