Файл: Дискретная математика- задания.pdf

Скачать файл (0,22Мб)

Заказать решение

ВУЗ: Национальная металлургическая академия Украины

Категория: Учебное пособие

Дисциплина: Маркетинг

Добавлен: 06.02.2019

Просмотров: 2073

Скачиваний: 7

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ємо множину S

шляхом вилучення з S

всіх входжень ¬L. S

суперечна тоді

і тільки тоді, коли S суперечна.

Правило чистих літер (ДП3). Літера L деякого диз’юнкта з S нази-

вається чистою в S тоді і тільки тоді, коли літера ¬L не з’являється ні в
якому диз’юнкті з S.

Правило розщеплення (ДП4). Якщо множину S можна подати у ви-

гляді (A

∨

∧

…

∧

∨

∧

∨

∧

…

∧

∨

∧

R, де A

, B

, i R

чисті від L i

L, S

= A

∧

…

∧

R i S

= B

∧

…

∧

R, то S супереч-

на тоді і тільки тоді, коли (S

∧

) суперечна.

Приклади вирішення задач з розділу Несуперечність і повнота чис-

лення висловлень

Довести, що ¬Р є логічним наслідком формул P

→ Q i ¬Q.

Розв’язок. За наслідком леми формула (P

→ Q) ∧ ¬Q → ¬P має бути

тавтологією. Користуючись таблицями істинності, знаходимо:

¬P

¬Q

→Q

→ Q) ∧ ¬Q

→ Q) ∧ ¬Q → ¬P

Отже, ¬Р є наслідком формул P

→ Q i ¬Q.

2. Довести, що S = (P

∨ Q ∨ ¬R) ∧ (P ∨ ¬Q) ∧ ¬P ∧ R ∧ U суперечна.

Розв’язок.

(1)

∨ Q ∨ ¬R) ∧ (P ∨ ¬Q) ∧ ¬P ∧ R ∧ U,

(2)

∨ ¬R) ∧ (¬Q) ∧ R ∧ U

– правило ДП2 з ¬P,

(3)

¬R

∧ R ∧ U

– правило ДП2 з ¬Q,

(4)

∧ U

– правило ДП2 з ¬R.

Оскільки останній диз’юнкт включає пустий диз’юнкт 0, то формула S су-
перечна.

3. Показати, що S = (P

∨ Q) ∧ ¬Q ∧ (¬P ∨ Q ∨ R) несуперечна.

Розв’язок.

(1)

∨ Q) ∧ ¬Q ∧ (¬P ∨ Q ∨ R),

(2)

∧ (¬P ∨ ¬R)

– правило ДП2 з ¬Q,

(3)

¬R

– правило ДП2 з P,

(4)

– правило ДП2 з ¬R.

Остання множина являє собою пустий диз’юнкт. Отже, S несуперечна.

АДАЧІ І ВПРАВИ З РОЗДІЛУ

ЕСУПЕРЕЧНІСТЬ І ПОВНОТА ЧИСЛЕННЯ ВИ-

СЛОВЛЕНЬ

1. Користуючись таблицями істинності, спробуйте впевнитись у тому, що

логічні зв’язки ¬,

∧, ∨, які розглядаються як операції над формулами,

задовольняють закони булевої алгебри.

2. Виясніть, чи є формулою числення висловлювань вираз:

a) (A

∧ B) C ¬D;

b) (A

∧ B) → C;

c) (A

→ B) ∧ ¬B;

d) (((¬A)

→ B) → ¬(C ∨ D)).

4. Скількома способами можна розставити дужки у таких виразах:

a) A

→ B ∨ ¬B ∧ C;

b) A

→ B → C → ¬A → ¬B;

c) A

∧ B ∨ C ∧ D ∧ C ∧∨ A?

5. Напишіть всі підформули формули:

a) (((A

→ B) ∧ (B → C)) → (¬A ∨ C));

b) ((A

→ B) → ((A → ¬B) → ¬B)).

5. Побудуйте таблиці істинності для таких формул:

a) ((P → Q)

∨ (P → (Q ∧ P)));

b) (¬P

→ ¬(Q ∧ P)) → (P ∨ R));

c) ((P

∧ (Q → P))→ ¬P);

d) (((P

∧ ¬Q) → Q) → (P → Q));

e) ((P

→ (Q ∨ R)) → ((P → Q) → (P → R)));

f) ((P

∧ (Q ∧ ¬P)) ∧ ((¬Q→ P) ∨ Q)).

6. Доведіть, що існують інтерпретації, в яких виконуються формули:

a) ¬(P

→ ¬P);

b) ((P

→ Q) → (Q → P));

c) ]((Q

→ (P ∧ R)) ∧ ¬ ((P ∨ R) → Q)).

7. Доведіть, що приведені нижче формули є тавтологією:

a) ((P

→ Q) ∨ (Q → P));

b) ((P

→ Q) ∨ (P → ¬Q));

c) (P

→ (Q → (P ∧ Q)));

d) ((P

→ Q) → ((Q → R) → (P → R)));

e) ((¬P

→ ¬Q) → (Q → P));

f) (P

→ (Q → P));

g) P

∨ ¬P;

h) (P

→ Q) → ((P → (Q → R)) → (P → R)));

i) (P

→ Q) → P;

j) P

→ (P ∨ Q);

k) Q

→ (P ∨ Q);

l) (P

∨ P) → P;

m) (¬P

→ (P → Q)).

8. При яких значеннях змінних x, y, z, u, v, w наведені нижче формули хибні:

a) (((x

→ (y∧ z)) → (¬y → ¬x)) → ¬y);

b) ((x

∧ y) ∨ (x ∧ z) ∨ (y ∧ z) ∨ (¬x ∧ ¬z);

c) (((x

∨ y) ∨ z) → ((x ∨ ) ∧ (x ∨ z)));

d) (((x

∨ y) ∧ ((y ∨ z) ∧ (z ∨ x))) → (( x ∧ y) ∧ z));

e) ((x

∨ y) → ((¬x ∧ y) ∨ (x ∧ ¬y)))?

9. Побудуйте доведення формули (А

→ В) = (¬В → ¬А), не користуючись

теоремою дедукції.

10. Знайдіть для формули ¬(А

→ (С

⇔

В))

→ D еквівалентну їй формулу,

яка містить лише логічні зв’язки:

∨ і ¬, ∧ і ¬.

11. Впевніться в тому, що аксіоми логіки висловлювань і аксіоми логіки

предикатів – тотожно істинні формули.

12. Знайдіть формулу логіки висловлювань, яка еквівалентна функції

f(x, y)

13. Покажіть, що відношення R на множині всіх формул логіки висловлю-

вань, яке визначається у вигляді ARB

⇔

h(A) = h(B) для інтерпретації h,

є відношенням еквівалентності.

14. Побудуйте інтерпретацію логіки висловлювань в алгебрі множин.

15. Чи буде логічним наслідком формула ¬C

∨ ¬D множини формул (C →

→ G) ∧ (D → S),

∧ G → E,

¬E?

16. Запищіть у вигляді формул числення висловлювань наведені нижче ви-

словлювання і знайдіть інтерпретації, при яких вони істинні.

a) Я піду до дому (Н) або залишусь тут і послухаю музику (S). Я не піду до

дому. Значить, я залишусь тут і послухаю музику.

b) Якщо Джон ляже спати сьогодні пізно (S), він буде вранці не в формі

(D). Якщо він ляже спати не пізно, то йому буде здаватися, що не варто

жити (L). Значить, або Джон завтра буде не в формі, або йому здавати-
меться, що йому не варто жити.

c) Заробітна плата зросте на (W), якщо буде інфляція (J). Якщо буде ін-

фляція, то збільшиться вартість життя (С). Заробітна плата зросте. Зна-
чить збільшиться вартість життя.

d) Якщо 2 – просте число (Р), то це найменше просте число (L). Якщо 2 –

найменше просте число, то 1 не є простим числом (N). Число 1 не є
простим числом. Значить, 2 – просте число.

e) Джон або перевтомився (Е), або хворий (S). Якщо він перевтомився, то

він дратується (С). Він не дратується. Значить він хворий.

f) Якщо я поїду автобусом (В), а автобус запізниться (L), то я пропущу

важливе побачення (М). Якщо я пропущу важливе побачення я почну
засмучуватись (D), то мені не слід їхати до дому (Н). Якщо я не отри-
маю цієї роботи (І), то я почну засмучуватись і мені треба поїхати до
дому. Значить, якщо я поїду автобусом і автобус запізниться, то я отри-
маю цю роботу.

g) Якщо 6 – складне число (S), то 12 – складне число (W). Якщо 12 –

складне число, то існує росте число, то існує просте число, більше, ніж

12 (Р). Якщо існує просте число, більше, ніж 12, то існує складне число
більше 12 (С). Якщо 6 ділиться на 2 (D), то 6 – складне число. Число 12
складне. Отже, 6 – складне число.

h) Якщо завтра буде холодно (С), я одягну тепле пальто (Н), якщо рукав

буде полагоджений (S). Завтра буде холодно, а рукав не буде полаго-
джений, значить, я не одягну тепле пальто.

17. Нехай Р(х) означає “х – просте число”, Е(х) – “х – парне число”, О(х) –

“непарне число”, D(x, y) – “у ділиться на х”. Перекладіть такі формули
логіки предикатів першого порядку:

a) P(7);

b) E(2)

∧ P(2);

∀

x (E(x)

∧ D(x, 6));

∀

(¬E(x)