ВУЗ: Национальная металлургическая академия Украины
Категория: Учебное пособие
Дисциплина: Маркетинг
Добавлен: 06.02.2019
Просмотров: 2040
Скачиваний: 7
26
f) x (P(x)
→ (
∃
y) (E(y)
∧ D(x, y)));
g)
∀
(O(x)
→ (
∀
y) (P(y)
→ ¬D(x, y)));
h) (
∃
x) (E(x)
∧ P(x)) ∧ ¬(
∃
x) ((E(x)
∧ P(x)) ∧ ((
∃
y) (x¬ = y
∧ E(x) ∧ P(y))).
18. Нижче наведено п’ять речень українською мовою, за якими йде стільки
ж речень символічної мови предикатів першого порядку. Знайдіть від-
повідні пари речень, так що кожний член пари був перекладом члена,
який йому відповідає.
a) Всі судді (J(x)) – юристи (L(x)).
b) Деякі юристи – шахраї (S(x)).
c) Не всі юристи – судді.
d) Жоден суддя не є шахраєм.
e) Деякі юристи – політики (Р(х)).
a')
∃
x (L(x))
∧ (S(x)).
b')
∃
x (L(x))
∧ (P(x)).
c') ’¬(
∀
x) (L(x)
→ J(x)).
d')
∀
x (J(x)
→ L(x)).
e')
∀
x (L(x)
→ ¬S(x)).
19. Вкажіть вільні і зв’язані входження змінних у таких формулах:
a)
∀
z (
∀
x A(x, y)
→ B(z, x));
b)
∀
y A(z, y)
→
∀
z A(z, y));
c) (
∀
y
∃
y (A(x, y, f(x, y)))
∨ ¬
∀
x B(y, f(x)).
20. Перекладіть на мову формул такі речення:
a) Не всі птахи можуть літати;
b) Або кожний любить кого-небудь, і ні один не любить всіх, або хтось
любить всіх, і хтось не любить нікого;
c) Якщо хтось може це зробити, то і я теж можу це зробити;
d) Не всі люди щирі і не всі щирі люди багаті.
21. Чи вільний терм f(x, y) для х у формулах А(х, у)
→
∀
x B(x), (
∀
y A(y, a))
∨
∃
y A(x, y)?
27
Р
ОЗДІЛ
З
АСТОСУВАННЯ ВИСЛОВЛЕНЬ МАТЕМАТИЧНОЇ ЛОГІКИ В КОНТАКТНИХ
СХЕМАХ
Приклади вирішення задач
1. Побудувати контактну схему висловлення, яка складається з трьох змінних,
має таблицю істинності 11101000. Її основні кон’юнкції надані в таблиці 1.
Таблиця 1
№
p q r
Задана таблиця
Основні кон’юнкції
1
1 1 1
1
p
∧
q
∧
r
2
1 1 0
1
p
∧
q
∧
¬r
3
1 0 1
1
p
∧
¬q
∧
r
4
1 0 0
0
p
∧
¬q
∧
¬r
5
0 1 1
1
¬p
∧
q
∧
r
6
0 1 0
0
¬p
∧
q
∧
¬r
7
0 0 1
0
¬p
∧
¬q
∧
r
8
0 0 0
0
¬p
∧
¬q
∧
¬r
Розв’язок. Використовуючи таблицю істинності, шукане висловлен-
ня запишемо формулою: (p
∧
q
∧
r)
∨
(p
∧
q
∧
¬r
∨
(p
∧
¬q
∧
r)
∨
(¬p
∧
q
∧
r)
Побудуємо відповідну контактну схему (малюнок 2).
Схема задовольняє такій умові: вона проводить струм тоді і тільки
тоді, коли замкнуті, принаймні, два з трьох контактів.
2. Використовуючи таблицю 1, побудувати схему з трьома незалежними
контактами, яка проводить струм якщо замкнуті лише два контакти.
p
q
r
p
q
r
p
q
r
p
q
r
(p * q * r) + (p * q * r`) + (p * q` * r) + (p` * q * r)
Рис.2
28
Розв’язок. Формула, що відповідає даній схемі приймає значення іс-
тина тоді і тільки тоді, коли це значення приймають дві з трьох змінних. p,
q, r. Це відповідає другому третьому і п'ятому рядкам таблиці 1. У цьому
випадку задана таблиця усієї формули 011010000, а сама формула має ви-
гляд:
(p
∧
q
∧
¬r)
∨
(p
∧
¬q
∧
¬r)
∨
(¬p
∧
q
∧
r).
Контактна схема, що моделює цю формулу представлена на малюнку 3.
Формулу запишемо у наступному вигляді – (p * q * r') + (p * q' * r) +
(p' * q * r).
При рішенні такого роду задач приймемо метод синтезу (побудови)
контактної схеми по їх характеристиках.
3. Визначити умови роботи заданої схеми. Знайти, при яких положеннях
контактів (малюнок 4) струм буде проходити або не проходити.
Розв’язок. Наданій схемі відповідає висловлення, вираз формулою:
p
∨
(¬p
∧
¬q
∨
(p
∧
q)
Задачі та вправи
1. Використовуючи основні послідовно сполучені схеми, побудуйте ме-
режі відповідним формулам:
a) p
→
q;
b) p
∨
q
c) p
↔
q
d) (p
→
q)
∨
q.
2. Накреслити схему, що відповідає формулі
(p
∧
¬q
∨
(¬p
∧
q)
∨
(¬p
∧
¬q)
3. Побудувати мережу, що відповідає формулі
((p
∨
q)
∧
r)
∨
((p
∧
r)
∨
q)
p
q
r`
p
q`
r
p`
q
r
Рис.3
p
p`
q`
p
q
p + (p` * q`)) + (p * q)
Рис.4
29
4. Побудуйте формулу схеми, яка зображення на малюнку 5?
5. Побудуйте схеми, які відповідають формулі:
(p
∧
q)
∨
(¬p
∧
r)
≡
(p
∨
r)
∧
(¬p
∨
q).
6. Побудуйте схему, що відповідала б таблиці з набором значень
10110100.
7. Машина – екзаменатор дає сигнал «залік» (запалюється лампочка) тоді і
тільки тоді, коли студент відповідає правильно хоча б на два з трьох пи-
тань квитка. При запровадженні в машину правильної відповіді замика-
ється контакт у ланцюзі сигнальної лампочки. Побудуйте схему й опи-
шіть її за допомогою правил логіки висловлень.
8. Складіть формулу, що відповідає приведеній на малюнку 6 схемі:
Побудувавши таблицю істинності формули, визначте умови, при яких
ланцюг буде проводити струм.
10. Побудуйте й опишіть за допомогою правил логіки висловлень схему
«електрифікованої версії» гри з моментами: «По встановленому сигналу
кожен гравець замикає або розмикає перемикач, яким він управляє. Як-
що обидва роблять те саме, то виграє гравець А; якщо ж вони роблять
протилежне те виграє гравець B». У схему введіть джерело току і лам-
почку. Побудуйте таку схему, щоб у випадку, коли виграє А, запалюва-
лося світло.
11. Накресліть схему з двома контактами, яка повинна замикатися тоді і тіль-
ки тоді, коли замкнутий або один, або інший контакт, але не обидва разом.
p
q
p`
q`
p
q
Рис.5
p
q
q`
p
p`
r
Рис.6
30
12. Складіть схему з трьома незалежними контактами, котра замкнута тоді і
тільки тоді, коли: a) замкнуті не більш чим два контакти; b) замкнутий
тільки один контакт; c) розімкнутий тільки один контакт.
13. Потрібно, щоб у кімнаті можна було включити і виключити світло за
допомогою любого з трьох перемикачів, розташованих на різних трьох
стінах. Побудувати й описати за допомогою правил логіки висловлень
таку схему.
14. Комітет, який складається з трьох чоловік, включно й голову, приймає
рішення більшістю голосів, однак рішення не може бути прийняте, якщо
за нього не проголосував голова. Голосування “за” проводиться натис-
ком кнопки, яка замикає контакт. У випадку прийняття рішення замига-
ється лампочка. Побудуйте схему, яка відповідає наведеним умовам.
15. Доведіть, що з’єднання S кінцевої кількості функціональних елементів
ϕ
1
, …
ϕ
m
є схемою тоді і тільки тоді, коли:
a) серед елементів
ϕ
i
є один і тільки один елемент з вільним виходом не
з’єднаним ні з яким із входів елементів
ϕ
j
(на кожному з виходів реалізу-
ється власна функція алгебри логіки);
b) вхід кожного з елементів
ϕ
i
може бути з’єднаний не більш чим з одним із
виходів елементів
ϕ
j
.
c) в S немає зворотних зв’язків.
16. Визначити умови роботи схеми, яка задана формулою:
p
∨
(¬p
∧
¬q
∨
(p
∧
q)
Знайти, при яких положеннях контактів струм буде проходити або не
проходити.
17. Чи отримаємо повну систему, якщо приєднаємо до елемента
ϕ
, який реа-
лізує функцію Шеффера
−
xy
елементи, котрі реалізують константи.
18. Побудувати таблицю істинності формули: (p
∧
¬q
∧
¬r)
∨
(¬p
∧
q
∧
r). Ви-
значити умови, при яких ланцюг буде проводити струм.
19. Побудуйте схему з чотирма контактами, котра повинна замикатися тоді
і тільки тоді, коли замкнуто два парні контакти. Наведіть формули такої
схеми. Побудуйте її таблицю істинності.