J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, де J, K, L, M, N — логічні змінні?

Рішення.

Вираз (N ∨ ¬N) істинно за будь-якого N, тому

J ∧ ¬K ∧ L ∧ ¬M = 0.

Застосуємо заперечення до обох частин логічного рівняння та використовуємо закон де Моргана (А ∧ В) = ¬ А ∨ ¬ В. Отримаємо ¬J ∨ K ∨ ¬L ∨ M = 1.

Логічна сума дорівнює 1, якщо хоча б одне із складових її висловлювань дорівнює 1. Тому отриманому рівнянню задовольняють будь-які комбінації логічних змінних крім випадку, коли всі врівняння величини рівні 0. Кожна з 4 змінних може бути або 1, або 0, тому всіляких комбінацій 2 · 2 · 2 · 2 = 16. Отже, рівняння має 16 -1 = 15 рішень.

Залишилося зауважити, що знайдені 15 рішень відповідають будь-якому з двох можливих значень значень логічної змінної N, тому вихідне рівняння має 30 рішень.

Відповідь: 30

Скільки різних рішень має рівняння

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

де J, K, L, M, N - логічні змінні?

У відповіді не потрібно перераховувати всі різні набори значень J, K, L, M і N, при яких виконана ця рівність. Як відповідь слід зазначити кількість таких наборів.

Рішення.

Використовуємо формули A → B = ¬A ∨ B і ¬(А ∨ В) = ¬А ∧ ¬В

Розглянемо першу підформулу:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Розглянемо другу підформулу

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Розглянемо третю підформулу

1) M → J = 1 отже,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Об'єднаємо:

K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 отже, 4 рішення.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Об'єднаємо:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L отже, 4 рішення.

в) M = 0; J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Відповідь: 4+4=8.

Відповідь: 8

Скільки різних рішень має рівняння

((K ∨ L) → (L ∧ M ∧ N)) = 0

де K, L, M, N - логічні змінні? У Відповіді не потрібно перераховувати всі різні набори значень K, L, M і N, при яких виконана ця рівність. Як відповідь Вам потрібно вказати кількість таких наборів.

Рішення.

перепишемо рівняння, використовуючи простіші позначення операцій:

((K + L) → (L · M · N)) = 0

1) з таблиці істинності операції «імплікація» (див. перше завдання) випливає, що ця рівність вірна тоді і тільки тоді, коли одночасно

K + L = 1 і L · M · N = 0

2) з першого рівняння випливає, що хоча одна зі змінних, K або L, дорівнює 1 (або обидві разом); тому розглянемо три випадки

3) якщо K = 1 і L = 0, то друга рівність виконується за будь-яких М і N; оскільки існує 4 комбінації двох логічних змінних (00, 01, 10 та 11), маємо 4 різні рішення

4) якщо K = 1 і L = 1, то друга рівність виконується за М · N = 0; існує 3 таких комбінації (00, 01 та 10), маємо ще 3 рішення

5) якщо K = 0, то обов'язково L = 1 (з першого рівняння); при цьому друга рівність виконується за М · N = 0; існує 3 таких комбінації (00, 01 та 10), маємо ще 3 рішення

6) всього отримуємо 4+3+3=10 рішень.

Відповідь: 10

Скільки різних рішень має рівняння

(K ∧ L) ∨ (M ∧ N) = 1

Рішення.

Вираз істинний у трьох випадках, коли (K ∧ L) і (M ∧ N) рівні відповідно 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N дорівнюють 1, а K і L будь-які, крім одночасно 1. Отже, 3 рішення.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 рішення.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 рішення.

Відповідь: 7.

Відповідь: 7

Скільки різних рішень має рівняння

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0

де X, Y, Z, P – логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень, при яких виконана ця рівність. Як відповідь вам потрібно вказати лише кількість таких наборів.

Рішення.

(X ∧ Y ∨ Z) ​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Логічне АБО хибно тільки в одному випадку: коли обидва вислови хибні.

Отже,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Отже, існує лише одне рішення рівняння.

Відповідь: 1

Скільки різних рішень має рівняння

(K ∨ L) ∧ (M ∨ N) = 1

де K, L, M, N - логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень K, L, M і N, при яких виконана ця рівність. Як відповідь вам потрібно вказати лише кількість таких наборів.

Рішення.

Логічне І істинно тільки в одному випадку: коли всі вирази істинні.

K ∨ L = 1, M ∨ N = 1.

Кожне із рівнянь дає по 3 рішення.

Розглянемо рівняння А ∧ В = 1 якщо і А і приймають справжні значення у трьох випадках кожне, то загалом рівняння має 9 рішень.

Отже, відповідь 9.

Відповідь: 9

Скільки різних рішень має рівняння

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

де A, B, C, D – логічні змінні?

У відповіді не потрібно перераховувати всі різні набори значень A, B, C, D, при яких виконана ця рівність. Як відповідь вам потрібно вказати кількість таких наборів.

Рішення.

Логічне "АБО" істинно, коли істинно хоча б одне із тверджень.

(D ∧ ¬D)= 0 за будь-яких D.

Отже,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, що дає нам 3 варіанти рішень при кожному D.

(D ∧ ¬ D)= 0 за будь-яких D, що дає нам два варіанти рішень (при D = 1, D = 0).

Отже: всього розв'язків 2*3 = 6.

Разом 6 рішень.

Відповідь: 6

Скільки різних рішень має рівняння

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

де K, L, M, N - логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень K, L, M і N, при яких виконана ця рівність. Як відповідь вам потрібно вказати лише кількість таких наборів.

Рішення.

Застосуємо заперечення до обох частин рівняння:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Логічне АБО істинно у трьох випадках.

Варіант 1.

K ∧ L ∧ M = 1, тоді K, L, M = 1, а L ∧ M ∧ N = 0. N будь-яке, тобто 2 рішення.

Варіант 2.

¬L ∧ M ∧ N = 1, тоді N, M = 1; L = 0, K будь-яке, тобто 2 рішення.

Отже, відповідь 4.

Відповідь: 4

A, B і С - цілі числа, для яких істинно висловлювання

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).

Чому дорівнює В, якщо A = 45 і C = 43?

Рішення.

Звернемо увагу, що цей складний вислів складається з трьох простих

1) ¬(А = B); (A > B)→(B > C); (B> A)→(С> B);

2) ці прості висловлювання пов'язані операцією ∧ (І, кон'юнкція), тобто вони повинні виконуватися одночасно;

3) з ¬(А = B)=1 відразу випливає, що AB;

4) припустимо, що A > B, тоді з другої умови отримуємо 1→(B > C)=1; цей вираз може бути істинним тоді і тільки тоді, коли B > C = 1;

5) тому маємо A > B > C, цій умові відповідає лише число 44;

6) про всяк випадок перевіримо і варіант A 0 → (B > C) = 1;

це вираз істинно за будь-якого B; тепер дивимося третю умову отримуємо

цей вираз може бути істинним тоді і тільки тоді, коли C > B, і тут ми отримали протиріччя, тому що немає такого числа B, для якого C > B > A.

Відповідь: 44.

Відповідь: 44

Складіть таблицю істинності для логічної функції

X = (А ↔ B) ∨ ¬(A → (B ∨ C))

в якій стовпець значень аргументу А являє собою двійковий запис числа 27, стовпець значень аргументу - числа 77, стовпець значень аргументу С - числа 120. Число в стовпці записується зверху вниз від старшого розряду до молодшого (включаючи нульовий набір). Переведіть отриманий двійковий запис значень функції X до десяткової системи числення.

Рішення.

Запишемо рівняння, використовуючи простіші позначення операцій:

1) це вираз із трьома змінними, у таблиці істинності буде рядків; отже, двійковий запис чисел, якими будуються стовпці таблиці А, У і З, має складатися з 8 цифр

2) переведемо числа 27, 77 і 120 у двійкову систему, відразу доповнюючи запис до 8 знаків нулями на початку чисел

3) навряд чи ви зможете одразу написати значення функції Х для кожної комбінації, тому зручно додати до таблиці додаткові стовпці для розрахунку проміжних результатів (див. таблицю нижче)

X0

А	У	З
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) заповнюємо стовпці таблиці:

А	У	З					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

значення дорівнює 1 тільки в тих рядках, де А = В

значення дорівнює 1 у тих рядках, де або В або С = 1

значення дорівнює 0 тільки в рядках, де А = 1 і В + С = 0

значення – це інверсія попереднього стовпця (0 замінюється на 1, а 1 – на 0)

результат Х (останній стовпець) - це логічна сума двох стовпців і

5) щоб отримати відповідь, виписуємо біти зі стовпця Х зверху донизу:

6) переводимо це число до десяткової системи:

Відповідь: 171

Яким є найбільше ціле число X, при якому істинно висловлювання (10 (X+1)·(X+2))?

Рішення.

Рівняння є операцією імплікації між двома відносинами:

1) Звичайно, тут можна застосувати той самий спосіб, що й у прикладі 2208, проте при цьому знадобиться вирішувати квадратні рівняння (не хочеться...);

2) Зауважимо, що за умовою нас цікавлять лише цілі числа, тому можна спробувати якось перетворити вихідний вираз, отримавши рівносильне висловлювання (точні значення коренів нас зовсім не цікавлять!);

3) Розглянемо нерівність: очевидно, що то, можливо як позитивним, і негативним числом;

4) Легко перевірити, що в області висловлювання істинно при всіх цілих, а в області - при всіх цілих (щоб не заплутатися, зручніше використовувати нестрогі нерівності, і замість і);

5) Тому для цілих можна замінити на рівносильний вираз

6) область істинності висловлювання - поєднання двох нескінченних інтервалів;

7) Тепер розглянемо друге нерівність: очевидно, що може бути як позитивним, і негативним числом;

8) В області висловлювання істинно при всіх цілих, а в області - при всіх цілих, тому для цілих можна замінити на рівносильний вираз

9) область істинності виразу - закритий інтервал;

10) Задане вираз істинно скрізь, крім областей, де і ;

11) Зверніть увагу, що значення вже не підходить, тому що там і , тобто імплікація дає 0;

12) При підставі 2, (10 (2+1) · (2+2)), або 0 → 0, що задовольняє умові.

Отже, відповідь 2.

Відповідь: 2

Яке найбільше ціле число X, за якого істинно висловлювання

(50 (X+1)·(X+1))?

Рішення.

Застосуємо перетворення імплікації та перетворюємо вираз:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Логічне АБО істинно коли істинно хоча б одне логічне висловлювання. Вирішивши обидві нерівності і враховуючи, що бачимо, що найбільше ціле число, при якому виконується хоча б одне з них – 7 (на малюнку жовтим зображено позитивне рішення другої нерівності, синім – першої).

Відповідь: 7

Вкажіть значення змінних К, L, M, N, за яких логічний вираз

(¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N)

помилково. Відповідь запишіть у вигляді рядка із 4 символів: значень змінних К, L, М та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що К=1, L=1, M=0, N=1.

Рішення.

Дублює завдання 3584.

Відповідь: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Рішення.

Застосуємо перетворення імплікації:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Застосуємо заперечення до обох частин рівняння:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Перетворюємо:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Отже, M = 0, N = 0, розглянемо тепер (¬K ∧ L ∨ M ∧ L):

з того, що M = 0, N = 0 випливає, що M ∧ L = 0, тоді K ∧ L = 1, тобто K = 0, L = 1.

Відповідь: 0100

Вкажіть значення змінних K, L, M, N, за яких логічний вираз

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

помилково. Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних K, L, M та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що K=1, L=1, M=0, N=1.

Рішення.

Запишемо рівняння, використовуючи простіші позначення операцій (умова «вираз хибно» означає, що воно дорівнює логічному нулю):

1) з формулювання умови випливає, що вираз має бути хибним тільки для одного набору змінних

2) з таблиці істинності операції «імплікація» випливає, що цей вираз хибний тоді і тільки тоді, коли одночасно

3) перша рівність (логічний твір дорівнює 1) виконується тоді і тільки тоді, коли і; звідси випливає (логічна сума дорівнює нулю), що можливо тільки при ; таким чином, три змінні ми вже визначили

4) з другої умови, , при і отримуємо .

Дублює завдання

Відповідь: 1000

Вкажіть значення логічних змінних Р, Q, S, Т, за яких логічний вираз

(Р ∨ ¬Q) ∨ (Q → (S ∨ Т)) помилково.

Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних Р, Q, S, T (у вказаному порядку).

Рішення.

(1) (Р ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Застосуємо перетворення імплікації:

¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.

Відповідь: 0100

Вкажіть значення змінних K, L, M, N, за яких логічний вираз

(K → M) ∨ (L ∧ K) ∨ ¬N

помилково. Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних K, L, M та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що K=1, L=1, M=0, N=1.

Рішення.

Логічне "АБО" хибне тоді і тільки тоді, коли хибні обидва твердження.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Застосуємо перетворення імплікації для першого виразу:

¬K ∨ M = 0 => K = 1, M = 0.

Розглянемо другий вираз:

(L ∧ K) ∨ ¬N = 0 (див. результат першого виразу) => L ∨ ¬N = 0 => L = 0, N = 1.

Відповідь: 1001.

Відповідь: 1001

Вкажіть значення змінних K, L, M, N, за яких логічний вираз

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

істинно. Відповідь запишіть у вигляді рядка із чотирьох символів: значень змінних K, L, M та N (у зазначеному порядку). Приміром, рядок 1101 відповідає тому, що K=1, L=1, M=0, N=1.

Рішення.

Логічне "І" істинно тоді і тільки тоді, коли істинні обидва твердження.

1) (K → M) = 1 Застосуємо перетворення імплікації: ¬K ∨ M = 1

2) (K → ¬M) = 1 Застосуємо перетворення імплікації: ¬K ∨ ¬M = 1

Звідси випливає, що K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Застосуємо перетворення імплікації: K ∨ (M ∧ ¬L ∧ N) = 1 з того, що K = 0 отримуємо.

Муніципальна бюджетна загальноосвітня установа

«Середня загальноосвітня школа №18»

міського округу місто Салават Республіки Башкортостан

Системи логічних рівнянь

у завданнях ЄДІ з інформатики

Розділ «Основи алгебри логіки» у завданнях ЄДІ вважається одним із найскладніших і погано вирішуваних. Середній відсоток виконання завдань на цю тему найнижчий і становить 43,2.

Розділ курсу	Середній відсоток виконання за групами завдань
Кодування інформації та вимірювання її кількості
Інформаційне моделювання
Системи числення
Основи алгебри логіки
Алгоритмізація та програмування
Основи інформаційно-комунікаційних технологій

Виходячи зі специфікації КІМу 2018 року, цей блок включає чотири завдання різного рівня складності.

№ завдання	Перевірені елементи змісту	Рівень складності завдання
	Вміння будувати таблиці істинності та логічні схеми
	Вміння здійснювати пошук інформації у мережі Інтернет
	Знання основних понять та законів математичної логіки
	Вміння будувати та перетворювати логічні вирази

Завдання 23 є високим за рівнем складності, тому має найнижчий відсоток виконання. Серед підготовлених випускників (81-100 балів) 49,8% виконавців, середньо підготовлені (61-80 балів) справляються на 13,7%, група учнів, що залишилася, дане завдання не виконує.

Успішність розв'язання системи логічних рівнянь залежить від знання законів логіки та від чіткого застосування методів розв'язання системи.

Розглянемо рішення системи логічних рівнянь шляхом відображення.

(23.154 Поляков К.Ю.) Скільки різних рішень має система рівнянь?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

де x1 , x2 ,…, x8, у1 ,у2 ,…,у8 - Логічні змінні? У відповіді не потрібно перераховувати всі різні набори значень змінних, при яких виконана ця рівність. Як відповідь слід зазначити кількість таких наборів.

Рішення. Всі рівняння, включені в систему, однотипні, і кожне рівняння включено чотири змінних. Знаючи x1 та y1, можемо знайти всі можливі значення x2 та y2, що задовольняють першому рівнянню. Розмірковуючи аналогічним чином, з відомих x2 і y2 можемо знайти x3, y3, що задовольняє друге рівняння. Тобто, знаючи пару (x1, y1) і визначивши значення пари (x2, y2), ми знайдемо пару (x3, y3), яка, у свою чергу, призведе до пари (x4, y4) і так далі.

Знайдемо всі рішення першого рівняння. Це можна зробити двома способами: побудувати таблицю істинності, через міркування та застосування законів логіки.

Таблиця істинності:

				x 1  y 1	x 2  y 2	(x 1  y 1 )  (x 2  y 2 )	(x 1  x 2 )	(y 1  y 2 )	(x 1  x 2 )  (y 1  y 2 )

Побудова таблиці істинності трудомістка і неефективна в часі, тому застосовуємо другий спосіб - логічні міркування. Твір дорівнює 1 і тоді, коли кожен множник дорівнює 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Розглянемо перше рівняння. Проходження дорівнює 1, коли 0 0, 0 1, 1 1, значить (x1 y1)=0 при (01), (10), то пара (x2  y2 ) може бути будь-який (00), (01), (10), (11), а при (x1 y1)=1, тобто (00) і (11) пара (x2 y2)=1 набуває таких же значень (00) та (11). Виключимо з цього рішення ті пари, для яких помилкові друге та третє рівняння, тобто x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

Загальна кількість пар 1+1+1+22= 25

2) (23.160 Поляков К.Ю.) Скільки різних рішень має система логічних рівнянь

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Рішення. 1) Рівняння однотипні, тому методом міркування знайдемо різні пари (x1, y1), (x2, y2) першого рівняння.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Рішенням другого рівняння є пари (00), (01), (11).

Знайдемо рішення першого рівняння. Якщо x1=0, то x2 , y2 - будь-які, якщо x1=1, то x2 , y2 набуває значення (11).

Складемо зв'язки між парами (x1, y1) та (x2, y2).

(x1 , y1 )	(x2 , y2 )

Складемо таблицю для обчислення кількості пар кожному етапі.

							0

Враховуючи рішення останнього рівняння x 7  y 7 = 1, виключимо пару (10). Знаходимо загальну кількість рішень 1+7+0+34=42

3)(23.180) Скільки різних рішень має система логічних рівнянь

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Рішення. 1) Рівняння однотипні, тому методом міркування знайдемо різні пари (x1, x2), (x3, x4) першого рівняння.

(x1  x2 )  (x3  x4 ) = 1

Виключимо з рішення пари, які в дотриманні дають 0 (1 0), це пари (01, 00, 11) та (10).

Складемо зв'язок між парами (x1,x2), (x3,x4)

Вирішення систем логічних рівнянь табличним способами перетворенням логічних виразів.

Ця методика заснована використання таблиць істинності, розрахована на учнів, які мають способами перетворення логічних выражений. Якщо учні погано володіють цими способами, можна використовувати без перетворення. (Ми використовуватимемо перетворення). Для оволодіння цим способом рішення, необхідні обов'язково знання властивостей основних логічних операцій: кон'юнкції, диз'юнкції, інверсії, імплікації та еквівалентності.

Алгоритм розв'язання систем рівнянь за цим методом:

Перетворити логічне рівняння, спростити його.

Визначити послідовність розв'язання рівнянь у системі, тому що в більшості випадків йде послідовне розв'язання рівнянь зверху вниз (як вони розташовані в системі), але є варіанти, коли зручніше, простіше почати вирішувати знизу вгору.

Побудувати таблицю змінних, де встановити початкові значення першої змінної (чи останньої).

Послідовно прописати можливі варіанти наступної змінної при кожномузначення першої.

Після вирішення попереднього рівняння, переходячи на наступне, обов'язково звертати увагу: які змінні використовуються в попередньому та наступному рівнянні, оскільки отримані при вирішенні попередніх рівняннях значення змінних переходять як варіанти для наступних рівнянь.

Звертати увагу до отримані кількості рішення під час переходу до наступної змінної, т.к. може бути виявлено закономірність збільшення рішень.

Приклад1.

¬ X1 ˅ X2=1

¬ X2 ˅ X3=1

¬ X3 ˅ X4=1

¬ X9 ˅ X10=1

Почнемо з Х1 і подивимося які значення ця змінна може набувати: 0 і 1.

Потім розглянемо кожне з цих значень і подивимося, яке може бути у своїй Х2.

Відповідь: 11 рішень

приклад 2.

( X1˄X2)˅(¬X1˄¬X2) ˅( X1↔ X3)=1

( X2˄X3)˅(¬X2˄¬X3) ˅( X2↔ X4)=1

(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0

Перетворимо за формулою (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B

Отримуємо:

( X1↔ X2) ˅ (X1↔ X3) =1

( X2↔ X3) ˅ (X2↔ X4) =1

( X8↔ X9) ˅ (X8↔ X10) =0

Для Х1 = 0 – 8 рішень

Візьмемо Х1=1 і подивимося які значення може набувати Х2. Тепер для кожного Х2 розглянемо які значення може набувати Х3 і т.д.

Для Х1 = 1 - 8 рішень

Разом 8+8=16 рішень

Відповідь. 16 рішень

Приклад 3 .

¬ ( X1↔ X2) ˄ ( X1 ˅X3) ˄ (¬X1 ˅ ¬X3 )=0

¬ ( X2↔ X3) ˄ (X2 ˅X4) ˄ (¬X2 ˅ ¬X4)=0

….

¬ ( X8↔ X9) ˄ (X8 ˅X10) ˄ (¬X8 ˅ ¬X10)=0

Після перетворень (A˅ B) ˄(¬ A ˅¬ B)= ¬( A ↔ B)

отримуємо:

¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0

¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0

…..

¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0

Візьмемо Х1=0 і подивимося які значення може набувати Х2. Тепер для кожного Х2 розглянемо які значення може набувати Х3 і т.д

Вийшло 10 рішень для Х1 = 0

Те саме проробимо для Х1=1. Отримаємо також 10 рішень

Разом: 10 +10 = 20

Відповідь: 20 рішень.

приклад 4.

(Х1 ˄ Х2) ˅ (¬Х1 ˄ ¬Х2) ˅ (Х2 ˄ Х3) ˅ (¬Х2 ˄¬ Х3)=1

(Х2 ˄ Х3) ˅ (¬Х2 ˄ ¬Х3) ˅ (Х3˄ Х4) ˅ (¬Х3 ˄¬ Х4)=1

….

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Перетворимо за формулами. (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B. Отримаємо:

(Х1↔ Х2) ˅ (Х2↔ Х3)=1

(Х2↔ Х3) ˅ (Х3↔ Х4)=1

(Х3↔ Х4) ˅ (Х4↔ Х5)=1

(Х4↔ Х5) ˅ (Х5↔ Х6)=1

(Х5↔ Х6) ˅ (Х6↔ Х7)=1

(Х6↔ Х7) ˅ (Х7↔ Х8)=1

(Х7↔ Х8) ˅ (Х8↔ Х9) = 1

(Х8↔ Х9) ˅ (Х9↔ Х10) = 0

Почнемо з кінця, тому що в останньому рівнянні змінні визначаться однозначно.

Нехай Х10=0, тоді Х9=1, Х8=0, Х7=0, Х6=0, а наступні змінні можуть набувати різних значень. Розглядатимемо кожне.

Разом 21 рішення для Х10 = 0

Тепер розглянемо Х10=1. Отримуємо також 21 рішення

Разом: 21 +21 = 42

Відповідь: 42 рішення

Приклад 5.

( X1 ˄X2) ˅ (¬X1 ˄ ¬X2) ˅ (¬X3 ˄X4) ˅ (X3 ˄ ¬X4)=1

( X3 ˄X4) ˅ (¬X3 ˄ ¬X4) ˅ (¬X5 ˄X6) ˅ (X5 ˄ ¬X6)=1

( X5 ˄X6) ˅ (¬X5 ˄ ¬X6) ˅ (¬X7 ˄X8) ˅ (X7 ˄ ¬X8)=1

( X7 ˄X8) ˅ (¬X7 ˄ ¬X8) ˅ (¬ X9 ˄X10) ˅ (X9˄ ¬X10) =1

Перетворимо за формулами:(¬ A ˄ B) ˅ ( A ˄ ¬ B)= A↔ ¬ B

( A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B

( X1↔ X2) ˅ (X3 ↔ ¬X4)=1

( X3↔ X4) ˅ (X5 ↔ ¬X6)=1

( X5↔ X6) ˅ (X7 ↔ ¬X8)=1

( X7↔ X8) ˅ (X9 ↔ ¬X10)=1

Розглянемо які значення можуть набувати Х1 і Х2: (0,0), (0,1), (1,0), (1,1).

Розглянемо кожен варіант та подивимося які значення при цьому можуть набувати Х3, Х4

Починаючи з Х7, Х8 відразу записуватимемо кількість рішень, оскільки відразу видно, що коли значення однакові (1,1) і (0,0), то наступні змінні мають 4 рішення, а коли різні (0,1) і (1 ,0) - 2 рішення.

Разом: 80+80+32=192

Відповідь:192 рішення

Приклад 6.

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

….

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Візьмемо Х1=0 і подивимося які значення може набувати Х2. Тепер для кожного Х2 розглянемо які значення може набувати Х3 і т.д.

Бачимо деяку закономірність: Кількість наступних рішень дорівнює сумі двох попередніх.

Те саме для Х1=1 отримуємо 89 рішень

Разом: 89 +89 = 178 рішень

Відповідь: 178 рішень

Вирішимо ще одним способом

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

….

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Введемо заміну:

T 1 =(Х1↔ Х2)

T 2 =(Х2↔ Х3)

T 3 =(Х3↔ Х4)

T 4 =(Х4↔ Х5)

T 5 =(Х5↔ Х6)

T 6 =(Х6↔ Х7)

T 7 =(Х7↔ Х8)

T 8 =(Х8↔ Х9)

T 9 =(Х9↔ Х10)

Отримуємо:

T1 ˅T2=1

T2 ˅T3=1

T3 ˅T4=1

T4 ˅T5=1

T5 ˅T6=1

T6 ˅T7=1

T7 ˅T8=1

T8 ˅T9=1

T9 ˅T10=1

ВізьмемоT1=1 і використовуємо властивості диз'юнкції:

А Згадаймо, що

T 1 =(Х1↔ Х2)

T 2 =(Х2↔ Х3) і т.д.

Скористаємося властивістю еквівалентності та переконаємось, дивлячись на таблицю, що

Коли Т = 1, виходить два рішення. Коли =0 –одне рішення.

Отже, можна підрахувати кількість одиниць та помножити їх на 2+ кількість нулів. Підрахунок, так само використовуючи закономірність.

Виходить, що кількість одиниць = попередньої загальної кількості рішень Т, а кількість нулів дорівнює попередній кількості одиниць

Отже. Отримаємо. Так як одиниця дає два рішення, то 34 * 2 = 68 рішень з одиниці +21 рішення з 0.

Разом 89 рішень для Т=1. Аналогічним способом отримуємо 89 рішень для Т=0

Разом 89 +89 = 178

Відповідь: 178 рішень

Приклад 7.

(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔ X2) ˅ ¬(X3↔ X4)=1

(X3 ↔ X4) ˅ (X5↔ X6) ˄ ¬(X3 ↔ X4) ˅ ¬(X5↔ X6)=1

(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔ X6) ˅ ¬(X7↔ X8)=1

(X7 ↔ X8) ˅ (X9↔ X10) ˄ ¬(X7 ↔ X8) ˅ ¬(X9↔ X10)=1

Введемо заміну:

T1=(X1 ↔ X2)

T2=(X3↔ X4)

T3=(X5↔ X6)

T4=(X7 ↔ X8)

T5=(X9↔ X10)

Отримаємо:

(Т1 ˅ Т2) ˄ ¬(Т1 ˅¬ Т2)=1

(Т2 ˅ Т3) ˄ ¬(Т2˅¬ Т3)=1

(Т3 ˅ Т4) ˄ ¬(Т3 ˅¬ Т4)=1

(Т4 ˅ Т5) ˄ ¬(Т4˅¬ Т5)=1

Розглянемо які можуть бути Т:

Т1

Т2

Т3

Т4

Т5

Разом

0

1

0

1

0

32

1

0

1

0

1

32

Т K ≠Т К+1 І Т K =Т К+2

Отримуємо: 2 5 =32 для Т

Разом: 32 +32 = 64

Відповідь: 64 рішення.

По завершенню року виявилося, що лише одне із трьох припущень є істинним. Які підрозділи отримали за підсумками року прибуток?

Рішення. Запишемо припущення з умови завдання у вигляді логічних висловлювань: «Отримання прибутку підрозділом B не є необхідною умовою для отримання

прибутку підрозділом A »: F 1 (A, B, C) = A → B

«Отримання прибутку хоча б одним підрозділів B і C не є достатнім для отримання прибутку підрозділом A»: F 2 (A, B, C) = (B + C) → A

«Підрозділи A і B не отримають прибуток одночасно»: F 3 (A, B, C) = A B

З умови відомо, що тільки одне з трьох припущень є істинним. Це означає, що ми повинні знайти якийсь із трьох наступних логічних виразів не є тотожно хибним:

1) F 1 F 2 F 3

2) F 1 F 2 F 3

3) F 1 F 2 F 3

1) (A → B) ((B + C) → A) (A ↔ B) = A B (B C + A) (A B + A B) = 0

2) (A → B) ((B + C) → A) (A ↔ B) = (A + B) (A B + A C) (A B + A B) = A B C

3) (A → B) ((B + C) → A) (AB) = (AB + B) (BC + A) (AB + A B) = 0

Отже, за підсумками істинним роки виявилося друге припущення, а перше і третє - помилковими.

									A = 0
	F1 F2 F3 = A B C = 1
									у тому й лише тому випадку, коли B = 0 .
									C = 1

Отже, прибуток отримає підрозділ C , а підрозділи A і B прибуток не отримають.

Розв'язання логічних рівнянь

У текстах державного централізованого тестування є завдання (А8), де пропонується знайти корінь логічного рівняння. Давайте розберемо способи вирішення таких завдань на прикладі.

Знайти корінь логічного рівняння: (A + B) (X AB) = B + X → A.

Перший спосіб розв'язання – побудова таблиці істинності. Побудуємо таблиці істинності правої та лівої частини рівняння та подивимося, при якому X , значення в останніх стовпцях цих таблиць збігатимуться.

F1 (A, B, X) = (A + B) (X AB)

					A + B	(A + B) (X AB)	F 1 (A, B, X)

F2 (A, B, X) = B + X → A

			X → A							F 2 (A, B, X)
					X → A			X → A

Порівняємо отримані таблиці істинності і виберемо ті рядки, в яких значення F 1 (A, B, X) і F2 (A, B, X) збігаються.

			F 1 (A, B, X)	F 2 (A, B, X)

Перепишемо лише вибрані рядки, залишивши лише стовпці аргументів. Подивимося на змінну X як функцію від A і B .

Вочевидь, що X = B → A .

Другий спосіб розв'язання – замінити знак рівності у рівнянні на знак еквіваленції, та був спростити отримане логічне рівняння.

Для полегшення подальшої роботи попередньо спростимо праву та ліву частини логічного рівняння та знайдемо їх заперечення:

F1 = (A + B) (X AB) = A + B + (X ↔ AB) = A B + X A B + X A + X B

F1 = (A + B) (X AB) = (A + B) (X A + X B + X A B) = X A B + X A B + X A B

F2 = B + X → A = B (X → A) = B (X + A) = X B + A B F2 = B + X → A = B + X + A = B + X A

Замінимо у нашому логічному рівнянні знак рівності на знак еквівалентності:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B + X A B + X A + X B) (X B + A B) +

+ (X A B + X A B + X A B) (B + X A) =

= (X A B + X B + X A B) + (X A B + X A B) =

Перегрупуємо логічні доданки даного виразу, винісши за дужку множники X і X .

X (AB) + X (B + AB) = X (AB) + X (B + A) =

Позначимо T = A B тоді

X T + X T = X ↔ T.

Отже, щоб логічне рівняння має розв'язок: X = A B = B + A = B → A .

Логічні елементи ЕОМ. Побудова функціональних схем

Математична логіка з розвитком ВТ опинилася у тісному взаємозв'язку з питаннями конструювання та програмування обчислювальної техніки. Алгебра логіки знайшла широке застосування спочатку під час розробки релейно-контактнихсхем. Першим фундаментальним дослідженням, яке звернуло увагу інженерів, котрі займалися проектуванням ЕОМ, можливість аналізу електричних ланцюгів з допомогою булевої алгебри опубліковано у грудні 1938 року статтю американця Клода Шеннона «Символічний аналіз релейно-контактних схем». Після цієї статті проектування ЕОМ не обходилося без застосування булевої алгебри.

Логічний елемент- це схема, що реалізує логічні операції диз'юнкції, кон'юнкції та інверсії. Розглянемо реалізацію логічних елементів через електричні релейно-контактні схеми, знайомі вам із шкільного курсу фізики.

Послідовне з'єднання контактів

Паралельне з'єднання контактів

Складемо таблицю залежностей стану ланцюгів від різних станів контактів. Введемо позначення: 1 – контакт замкнутий, струм у ланцюзі є; 0 – контакт розімкнуто, струму в ланцюзі немає.

		Стан ланцюга з	Стан ланцюга з паралельним
		послідовним з'єднанням	з'єднанням

Як видно, ланцюг з послідовним з'єднанням відповідає логічній операції кон'юнкція, так як струм у ланцюзі з'являється лише при одночасному замиканні контактів A і B. Ланцюг з паралельним з'єднанням відповідає логічної операції диз'юнкції, так як струм в ланцюзі відсутня тільки в момент, коли обидва контакти розімкнуті.

Логічна операція інверсії реалізується через контактну схему електромагнітного реле, принцип якого вивчається у шкільному курсі фізики. Контакт x розімкнуто, коли x замкнено, і навпаки.

Використання релейно-контактних елементів для побудови логічних схем обчислювальних машин не виправдало себе через низьку надійність, великі габарити, велике енергоспоживання і низьку швидкодію. Поява електронних приладів (вакуумних та напівпровідникових) створила можливість побудови логічних елементів із швидкодією від 1 мільйона перемикань на секунду та вище. Логічні елементи на напівпровідниках працюють як ключа аналогічно електромагнітному реле. Вся теорія, викладена контактних схем, переноситься на напівпровідникові елементи. Логічні елементи на напівпровідниках характеризуються не станом контактів, а наявністю сигналів на вході та виході.

Розглянемо логічні елементи, що реалізують основні логічні операції:

Інвертор – реалізує операцію заперечення чи інверсію. У

інвертора один вхід та один вихід. Сигнал на виході з'являється

тоді, коли на вході його немає, і навпаки.

Кон'юнктор -

X1 X 2 ... X n

реалізує операцію кон'юнкції.

У кон'юнктора

один вихід та не менше двох входів. Сигнал на

виході з'являється тоді і лише тоді, коли на

всі входи подані сигнали.

X 2 + ... X n

Диз'юнктор – реалізує операцію диз'юнкції. У

диз'юнктора один вихід і не менше двох

Сигнал на виході не з'являється тоді і лише тоді,

коли всі входи не подано сигнали.

	Побудувати	функціональну
F(X, Y, Z) = X (Y + Z)
			X+Z

схему, що відповідає функції:

& F(X, Y, Z)

Розв'язання задач з використанням кон'юнктивно-нормальної

і диз'юнктивно-нормальноїформ

У задачниках по логіці часто зустрічаються стандартні завдання, де потрібно записати функцію, що реалізуєрелейно-контактну схему, спростити її та побудувати таблицю істинності для цієї функції. А як вирішувати обернене завдання? Дано довільну таблицю істинності, потрібно побудувати функціональну або релейно-контактну схему. Цим питанням ми займемося сьогодні.

Будь-яку функцію алгебри логіки можна уявити комбінацією трьох операцій: кон'юнкції, диз'юнкції та інверсії. Давайте розберемося, як це робиться. Для цього запишемо кілька визначень.

Мінтерм - це функція, утворена кон'юнкцією певної кількості змінних чи його заперечень. Мінтерм приймає значення 1 при одному з усіх можливих наборів

аргументів, і значення 0 за всіх інших. Приклад: x 1 x 2 x 3 x 4 .

Макстерм - це функція, утворена диз'юнкцією певної кількості змінних чи його заперечень. Макстерм приймає значення 0 в одному з можливих наборів і 1 при всіх інших.

Приклад: x1+x2+x3.

Функція у диз'юнктивної нормальної форми(ДНФ) є логічною сумою мінтермів.

Приклад: x 1 x 2 + x 1 x 2 + x 1 x 2 x 3 .

Кон'юнктивна нормальна форма(КНФ) є логічним добутком елементарних диз'юнкцій (макстермів).

Приклад: (x 1 + x 2 + x 3) (x 1 + x 2).

Досконала диз'юнктивно-нормальна форма називається ДНФ, у кожному мінтермі якої є всі змінні або їх заперечення.

Приклад: x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

Досконала кон'юктивно-нормальна форма називається КНФ, у кожному макстермі якої є всі змінні або їх заперечення.

Приклад: (x 1 + x 2 + x 3) (x 1 + x 2 + x 3)

Запис логічної функції за таблицею

Будь-яка логічна функція може бути виражена у вигляді СДНФ чи СКНФ. Як приклад розглянемо функцію f представлену в таблиці.

			f(x1, x2, x3)

Функції G0, G1, G4, G5, G7 – це мінтерми (див. визначення). Кожна з цих функцій є твором трьох змінних або їх інверсій та набуває значення 1 лише в одній ситуації. Видно, що для того щоб отримати 1 у значенні функції f, потрібен один мінтерм. Отже, кількість мінтермів, що становлять СДНФ цієї функції, дорівнює кількості одиниць у значенні функції: f = G0 + G1 + G4 + G5 + G7. Таким чином, СДНФ має вигляд:

f (x 1, x 2 , x 3 ) = x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3.

Аналогічно можна збудувати СКНФ. Кількість співмножників дорівнює кількості нулів у значеннях функції:

f (x 1, x 2, x 3) = (x 1 + x 2 + x 3) (x 1 + x 2 + x 3) (x 1 + x 2 + x 3).

Таким чином можна записати у вигляді формули будь-яку логічну функцію, задану у вигляді таблиці.

Алгоритм побудови СДНФ за таблицею істинності

Дана таблиця істинності деякої функції. Для побудови СДНФ необхідно виконати таку послідовність кроків:

1. Вибрати всі рядки таблиці, в яких функція набирає значення 1.

2. Кожному такому рядку поставити у відповідність кон'юнкцію всіх аргументів або їх інверсій (мінтерм). При цьому аргумент, що набирає значення 0, входить у мінтерм із запереченням, а значення 1 – без заперечення.

3. Нарешті утворюємо диз'юнкцію всіх отриманих мінтермів. Кількість мінтермів має збігатися з кількістю одиниць логічної функції.

Алгоритм побудови СКНФ за таблицею істинності

Дана таблиця істинності деякої функції. Для побудови СКНФ необхідно виконати таку послідовність кроків:

1. Вибрати всі рядки таблиці, в яких функція набирає значення 0.

2. Кожному такому рядку поставити у відповідність диз'юнкцію всіх аргументів або їх інверсій (макстерм). При цьому аргумент, який набирає значення 1, входить у макстерм з запереченням, а значення 1 – без заперечення.

3. Нарешті утворюємо кон'юнкцію всіх отриманих макстермів. Кількість макстермів має збігатися з кількістю нулів логічної функції.

Якщо домовитися з двох форм (СДНФ або СКНФ) віддавати перевагу тій, яка містить менше літер, то СДНФ краще, якщо серед значень функції таблиці істинності менше одиниць, СКНФ – якщо менше нулів.

приклад. Дано таблицю істинності логічної функції від трьох змінних. Побудувати логічну формулу, що реалізує цю функцію.

			F(A, B, C)

Виберемо ті рядки у цій таблиці істинності, у яких значення функції дорівнює 0.

F(A, B, C) = (A + B + C) (A + B + C)

Перевіримо виведену функцію, склавши таблицю істинності.

Порівнявши початкову і підсумкову таблицю істинності можна дійти невтішного висновку, що логічна функція побудована правильно.

Вирішення задач

1. Три викладачі відбирають завдання для олімпіади. На вибір пропонується кілька завдань. За кожним завданням кожен із викладачів висловлює свою думку: легке (0) чи важке (1) завдання. Завдання включається до олімпіадного завдання, якщо не менше двох викладачів відзначили його як важке, але якщо всі три викладачі вважають його важким, то таке завдання не включається до олімпіадного завдання як надто складне. Складіть логічну схему пристрою, який видаватиме на виході 1, якщо завдання включається в олімпіадне завдання, і 0, якщо не включається.

Побудуємо таблицю істинності шуканої функції. У нас є три вхідні змінні (три викладачі). Отже, потрібна функція буде функцією від трьох змінних.

Аналізуючи умову завдання, отримуємо таку таблицю істинності:

Будуємо СДНФ. F(A, B, C) = ABC + ABC + ABC

Тепер будуємо логічну схему цієї функції.

B & 1 F(A,B,C)

2. Міська олімпіада з базового курсу інформатики, 2007 рік.Побудуйте схему електричного ланцюга для під'їзду триповерхового будинку таку, щоб вимикачем на будь-якому поверсі можна було б увімкнути або вимкнути світло у всьому будинку.

Отже, у нас є три вимикачі, якими ми повинні вмикати та вимикати світло. Кожен вимикач має два стани: верхній (0) і нижній (1). Припустимо, якщо всі три вимикача в положенні 0, світло в під'їзді вимкнено. Тоді при переведенні будь-якого з трьох вимикачів у положення 1 світло в під'їзді має спалахнути. Очевидно, що при переведенні будь-якого іншого вимикача в положення 1 світло в під'їзді вимкнеться. Якщо третій перемикач перевести в положення 1, світло в під'їзді загориться. Будуємо таблицю істинності.

Тоді F(A, B, C) = ABC + ABC + ABC + ABC .

	3. Умова зміни			значення логічної функції			F(A, B, C) = C →		A + B
	одночасної зміни аргументів B і C дорівнює:
		A → (BC)						(BC) → A
					A(BC)
	4) (BC) → A				A → (BC)

Примітка. Для успішного розв'язання цієї задачі пригадаємо такі логічні формули:

x → y = x + y x y = x y + x y

x ↔ y = x y + x y

Нам дана логічна функція від трьох змінних F 1 (A, B, C) = C → A + B = C + A B .

Змінимо одночасно змінні B і C: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Побудуємо таблиці істинності цих двох функций:

Аналізуємо отриману таблицю. З восьми рядків таблиці лише у двох (2-й та 3-й) функція не змінює свого значення. Зверніть увагу, що у цих рядках змінна A не змінює свого значення протилежне, а змінні B і C – змінюють.

Будуємо СКНФ функції за цими рядками:

F3 (A, B, C) = (A + B + C) (A + B C) = A + AB + AC + AB + BC + AC + BC = .

A + (B ↔ C) = A + B C = (BC) → A

Отже, потрібна відповідь – 4.

4. Умова зміни значення логічної функції F (A, B, C) = C + AB при одночасному зміні аргументів A і B дорівнює:

1) C + (AB)

C + (A B)

C(A B)

4) C(A B)

C → (A B)

F 1 (A, B, C) =

C + AB

F 2 (A , B ,C ) = F 1 (

C) = A

Будуємо таблицю істинності.

Аналізуємо отриману таблицю. З восьми рядків таблиці лише у двох (1-й та 7-й) функція змінює своє значення. Зверніть увагу, що в цих рядках змінна не змінює своє значення, а змінні A і B – змінюють.

Будуємо СДНФ функції за цими рядками:

F3 (A, B, C) = A B C + A B C = C(A B + A B) = C(A ↔ B) = C + (A B)

Отже, потрібна відповідь – 2.

Використана література

1. Шапіро С.І. Розв'язання логічних та ігрових завдань(логіко-психологічні етюди). - М.: Радіо і зв'язок, 1984. - 152 с.

2. Шоломов Л.А. Основи теорії дискретних логічних та обчислювальних пристроїв. - М.: Наука. Гол. ред. фіз. - мат. літ., 1980. – 400 с.

3. Пухальський Г.І., Новосельцева Т.Я. Проектування дискретних пристроїв на інтегральних мікросхемах: Довідник. - М.: Радіо і зв'язок, 1990.

Рішення рівняння 1.Перейти до префіксної форми запису рівняння, замінивши позначення заперечень на ¬2.Побудувати заголовок таблиці істинності спеціального виду для X = F (А, B) 5.По таблиці істинності визначити вид функції X, за необхідності скориставшись методами побудови СКНФ та СДНФ, які будуть розглянуті нижче.

Побудова таблиці істинності спеціального виду ¬((А+B)·(X A·B))=¬(B+¬(X A))

Таблиця істинності X=F(A, B) ABX Відповідає запереченню імплікації В А ВІДПОВІДЬ:

Комбінаційні схеми логічних пристроїв Базисні елементи (ГОСТ): 1 А В Диз'юнкція А В Еквівалентність & А В Кон'юнкція M2 А В XOR

Комбінаційні схеми логічних пристроїв Базисні елементи (ГОСТ): 1 А В Імплікація & А В Елемент Шеффера & А В Коімплікація 1 А В Елемент Вебба

Приклад схеми F 1 & 1 & & 1M2 B A

Рішення схем 1 Варіант - перетворення схеми на складне логічне вираження і потім - спрощення його за законами логіки. 2 Варіант – побудова таблиці істинності, а потім, за необхідності, побудова через СКНФ чи СДНФ (див. нижче). Розглянемо другий варіант, як простіший і зрозуміліший.

Побудова таблиці істинності AB A + B + · B B · A + A B A +

Таблиця істинності F(A, B) ABX Відповідає запереченню імплікації В А ВІДПОВІДЬ:

СДНФ і СКНФ (визначення) Елементарною кон'юнкцією називається кон'юнкція декількох змінних, взятих з запереченням або без заперечення, причому серед змінних можуть бути однакові. назвемо нормальною диз'юнктивною формою (ДНФ) Будь-яку кон'юнкцію елементарних диз'юнкцій назвемо нормальною кон'юнктивною формою (ДНФ)

СДНФ і СКНФ (визначення) Досконала диз'юнктивна нормальна форма (СДНФ), називається ДНФ, в якій немає однакових елементарних кон'юнкцій і всі кон'юнкції складаються з одного і того ж набору змінних, в який кожна змінна входить тільки один раз (можливо з запереченням). Досконала кон'юнктивна нормальна форма (СКНФ), називається КНФ, в якій немає однакових елементарних диз'юнкцій і всі диз'юнкції складаються з одного і того ж набору змінних, в який кожна змінна входить тільки один раз (можливо з запереченням).

Алгоритм отримання СДНФ за таблицею істинності 1.Визначити рядки таблиці істинності в останньому стовпці яких стоять 1. 2.Виписати для кожного зазначеного рядка кон'юнкцію всіх змінних наступним чином: якщо значення змінної в даному рядку дорівнює 1, то в кон'юнкцію включати саму цю змінну, дорівнює 0, то її заперечення. 3.Всі отримані кон'юнкції зв'язати у диз'юнкцію. Алгоритм отримання СКНФ за таблицею істинності 1.Визначити рядки таблиці істинності в останньому стовпці яких стоять 0. 2.Виписати для кожного зазначеного рядка диз'юнкцію всіх змінних наступним чином: якщо значення змінної в даному рядку дорівнює 0, то в кон'юнкцію включати саму цю змінну одно 1, то її заперечення. 3.Всі отримані диз'юнкції зв'язати у кон'юнкцію.

Приклад побудови СKНФ XY F(X,Y) Відзначити нулі 2. Диз'юнкції: X + Y 3. Кон'юнкція: (X + Y) · (X + Y)