Складання таблиці істинності логічного виразу онлайн. Тотожні перетворення логічних виразів

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

Мета уроку:

1. Навчальні:
   1. Навчити складати логічні вирази з висловлювань
   2. Ввести поняття "таблиця істинності"
   3. Вивчити послідовність дій побудови таблиць істинності
   4. Навчити знаходити значення логічних виразів за допомогою побудови таблиць істинності
   5. Ввести поняття равносильности логічних виразів
   6. Навчити доводити равносильность логічних виразів, використовуючи таблиці істинності
   7. Закріпити навички знаходження значень логічних виразів за допомогою побудови таблиць істинності
2. Розвиваючі:
   1. Розвивати логічне мислення
   2. розвивати увагу
   3. розвивати пам'ять
   4. Розвивати мова учнів
3. виховні:
   1. Виховувати вміння слухати вчителя і однокласників
   2. Виховувати акуратність ведення зошита
   3. виховувати дисциплінованість

Хід уроку

організаційний момент

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

Перевірка домашнього завдання

Записати рішення домашніх завдань на дошку
Всі інші відкрийте зошити, я пройду, перевірю, як ви виконали домашнє завдання
Давайте ще раз повторимо логічні операції
В якому випадку в результаті операції логічного множення складене висловлювання було це слово?
Складене висловлювання, утворене в результаті операції логічного множення, істинно тоді і тільки тоді, коли істинні всі вхідні в нього прості висловлювання.
В якому випадку в результаті операції логічного складання складене висловлювання буде хибно?
Складене висловлювання, утворене в результаті операції логічного додавання, помилково тоді, коли помилкові всі вхідні в нього прості висловлювання.
Як впливає інверсія на висловлювання?
Інверсія робить справжнє висловлювання помилковим і, навпаки, помилкове - істинним.
Що ви можете сказати про імплікації?
Логічне слідування (імплікація) утворюється з'єднанням двох висловлювань в одне за допомогою обороту мови «якщо ..., то ...».
позначається А-> В
Складене висловлювання, утворене за допомогою операції логічного слідування (імплікації), помилково тоді і тільки тоді, коли з істинної передумови (першого висловлювання) слід помилковий висновок (друге висловлювання).
Що ви можете сказати про логічної операції еквівалентності?
Логічне рівність (еквівалентність) утворюється з'єднанням двох висловлювань в одне за допомогою обороту мови "... тоді і тільки тоді, коли ...", "... в тому і тільки в тому випадку ..."
Складене висловлювання, утворене за допомогою логічної операції еквівалентності істинно тоді і тільки тоді, коли обидва висловлювання одночасно або хибні, або істинні.

Пояснення нового матеріалу

Добре, повторили пройдений матеріал, переходимо до нової теми.

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

Ще раз розглянемо наш приклад з минулого уроку

і побудуємо таблицю істинності для цього складного висловлювання

При побудові таблиць істинності є певна послідовність дій. Давайте запишемо

1. Необхідно визначити кількість рядків в таблиці істинності.

• кількість рядків \u003d 2 n, де n - кількість логічних змінних

Необхідно визначити кількість стовпців в таблиці істинності, яка дорівнює кількості логічних змінних плюс кількість логічних операцій.

Необхідно побудувати таблицю істинності з вказаною кількістю рядків і стовпців, ввести назви стовпців таблиці відповідно до послідовності виконання логічних операцій з урахуванням дужок і пріоритетів;

Заповнити стовпці вхідних змінних наборами значень

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

Записали. Будуємо таблицю істинності
Що ми робимо по-перше?
Визначити кількість стовпців в таблиці
Як ми це робимо?
Вважаємо кількість змінних. У нашому випадку логічна функція містить 2 змінні
Які?
А та В
Значить скільки рядків буде в таблиці?
Кількість рядків в таблиці істинності має дорівнювати 4.
А якщо 3 змінних?
Кількість рядків \u003d 2³ \u003d 8
Вірно. Що робимо далі?
Визначаємо кількість стовпців \u003d кількості логічних змінних плюс кількість логічних операцій.
Скільки буде в нашому випадку?
У нашому випадку кількість змінних дорівнює двом, а кількість логічних операції - п'яти, тобто кількість стовпців таблиці істинності одно семи.
Добре. Далі?
Будуємо таблицю з вказаною кількістю рядків і стовпців, позначаємо стовпці і вносимо в таблицю можливі набори значень вихідних логічних змінних і заповнюємо таблицю істинності по стовпцях.
Яку операцію будемо виконувати першою? Тільки враховуйте дужки і пріоритети
Можна спочатку виконати логічне заперечення або знайти значення спочатку в першій скобці, потім інверсію і значення в другій скобці, потім значення між цими дужками

					┐Аv┐В	(AvB) & (┐Av┐B)

Тепер ми можемо визначити значення логічної функції для будь-якого набору значенні логічних змінних
Тепер записуємо пункт "Рівносильні логічні вирази".
Логічні вирази, у яких останні стовпці таблиць істинності збігаються, називаються рівносильними.Для позначення рівносильних логічних виразів використовується знак "\u003d",
Доведемо, що логічні вирази ┐ А & ┐В і AvB рівносильні. Побудуємо спочатку таблицю істинності логічного виразу

Скільки стовпців буде в таблиці? 5
Яку операцію будемо виконувати першою? Інверсію А, інверсію В

				┐А & ┐В

Тепер побудуємо таблицю істинності логічного виразу AvB
Скільки рядків буде в таблиці? 4
Скільки стовпців буде в таблиці? 4

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

			┐ (AvB)

Побудували таблиці. Тепер давайте, порівняємо значення в останніх шпальтах таблиць істинності, тому що саме останні стовпці є результуючими. Вони збігаються, отже, логічні вирази рівносильні і ми можемо поставити між ними знак "\u003d"

Розв'язання задач

1.

Скільки змінних містить дана формула? 3
Скільки рядків і стовпців буде в таблиці? 8 і 8
Яка буде в нашому прикладі послідовність операцій? (Інверсія, операції в дужках, операцію за дужки)

					Bv┐B (1)	(1) \u003d\u003e ┐C	Av (Bv┐B \u003d\u003e ┐C)

2. Доведіть за допомогою таблиць істинності равносильность наступних логічних виразів:

(А → B) І (Av┐B)

Який робимо висновок? Дані логічні вирази не рівносильні

Домашнє завдання

Довести, використовуючи таблиці істинності, що логічні вирази

┐A v ┐B і А & В рівносильні

Пояснення нового матеріалу (продовження)

Ми вже кілька уроків поспіль використовуємо поняття "таблиця істинності", а що ж таке таблиця істинності, як ви думаєте?
Таблиця істинності - це таблиця, що встановлює відповідність між можливими наборами значень логічних змінних і значеннями функцій.
Як ви впоралися з домашнім завданням, який у вас вийшов висновок?
вирази рівносильні
Пам'ятайте, на попередньому уроці ми з складного висловлювання становили формулу, замінюючи прості висловлювання 2 * 2 \u003d 4 і 2 * 2 \u003d 5 змінними А і В
Тепер давайте вчитися складати логічні вирази з висловлювань

Запишіть завдання

Записати у вигляді логічної формули висловлювання:

1) Якщо Іванов здоровий і багатий, то він здоровий

Аналізуємо висловлювання. Виявляємо прості висловлювання

А - Іванов здоровий
В - Іванов багатий

Добре, тоді як буде виглядати формула? Тільки не забудьте, щоб не втрачався сенс висловлювання, розставити дужки у формулі

2) Число є простим, якщо воно ділиться тільки на 1 і саме на себе

А - число ділиться тільки на 1
В - число ділиться тільки на себе
С - число є простим

3) Якщо число ділиться на 4, воно ділиться на 2

А - ділиться на 4
В - ділиться на 2

4) Довільно узяте число або ділиться на 2, або ділиться на 3

А - ділиться на 2
В - ділиться на 3

5) Спортсмен підлягає дискваліфікації, якщо він некоректно поводиться по відношенню до суперника або судді, і якщо він брав «допінг».

А - спортсмен підлягає дискваліфікації
В - некоректно поводиться по відношенню до суперника
З - некоректно поводиться по відношенню до судді
D - приймав «допінг».

Розв'язання задач

1. Побудувати таблицю істинності для формули

((P & q) → (p → r)) v p

Пояснюємо скільки рядків і стовпців буде в таблиці? (8 і 7) Яка буде послідовність операцій і чому?

					(P & q) → (p → r)	((P & q) → (p → r)) v p

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

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

2. Записати у вигляді логічної формули висловлювання:

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

1. Якщо капітан корабля отримує спеціальну вказівку, то він повинен покинути порт на своєму кораблі
2. Якщо капітан не отримує спеціального вказівки, то він не повинен залишати порт, або він надалі позбавляється допуску в цей порт
3. Капітан або позбавляється допуску в цей порт, або не отримує спеціального вказівки

Виявляємо прості висловлювання, складаємо формули

• А - капітан отримує спеціальну вказівку
• В - залишає порт
• З - позбавляється допуску в порт

1. ┐А → (┐В v С)
2. З v ┐А

3. Записати складене висловлювання "(2 * 2 \u003d 4 і 3 * 3 \u003d 9) або (2 * 2 ≠ 4 і 3 * 3 ≠ 9)" в формі логічного виразу. Побудувати таблицю істинності.

А \u003d (2 * 2 \u003d 4) B \u003d (3 * 3 \u003d 9)

(А & В) v (┐А & ┐В)

					┐А & ┐В	(А & В) v (┐А & ┐В)

Домашнє завдання

Вибрати складене висловлювання, що має ту ж таблицю істинності, що й не (НЕ А і не (В і С)).

1. АІВ або СІА;
2. (А чи В) і (А або С);
3. А та (В або С);
4. А чи (не в чи не С).

визначення 1

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

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

визначення 2

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

визначення 3

рівносильними називаються логічні вирази, останні стовпці таблиць істинності яких збігаються. Равносильность позначається за допомогою знака $ «\u003d» $.

При складанні таблиці істинності важливо враховувати наступний порядок виконання логічних операцій:

Малюнок 1.

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

Алгоритм побудови таблиці істинності логічної функції

Визначають кількість рядків: кількість рядків \u003d $ 2 ^ n + 1 $ (Для рядка заголовка), $ N $ - кількість простих виразів. Наприклад, для функцій двох змінних існує $ 2 ^ 2 \u003d 4 $ комбінації наборів значень змінних, для функцій трьох змінних - $ 2 ^ 3 \u003d 8 $ і т.д.

Визначають кількість стовпців: кількість стовпців \u003d к-ть змінних + к-ть логічних операцій. При визначенні кількості логічних операцій враховують також порядок їх виконання.

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

Малюнок 2.

приклад 1

Скласти таблицю істинності логічного виразу $ D \u003d \\ bar (A) \\ vee (B \\ vee C) $.

Рішення:

Визначимо кількість рядків:

кількість рядків \u003d $ 2 ^ 3 + 1 \u003d 9 $.

Кількість змінних - $ 3 $.

1. інверсія ($ \\ bar (A) $);
2. диз'юнкція, тому що вона знаходиться в дужках ($ B \\ vee C $);

3. диз'юнкція ($ \\ overline (A) \\ vee \\ left (B \\ vee C \\ right) $) - шукане логічне вираз.

   Кількість стовпців = $3 + 3=6$.

Заповнимо таблицю, враховуючи таблиці істинності логічних операцій.

Малюнок 3.

приклад 2

За даним логічного виразу побудувати таблицю істинності:

Рішення:

Визначимо кількість рядків:

Кількість простих виразів - $ n \u003d 3 $, значить

кількість рядків = $2^3 + 1=9$.

Визначимо кількість стовпців:

Кількість змінних - $ 3 $.

Кількість логічних операцій і їх послідовність:

1. заперечення ($ \\ bar (C) $);
2. диз'юнкція, тому що вона знаходиться в дужках ($ A \\ vee B $);
3. кон'юнкція ($ (A \\ vee B) \\ bigwedge \\ overline (C) $);
4. заперечення, яке позначимо $ F_1 $ ($ \\ overline ((A \\ vee B) \\ bigwedge \\ overline (C)) $);
5. диз'юнкція ($ A \\ vee C $);
6. кон'юнкція ($ (A \\ vee C) \\ bigwedge B $);
7. заперечення, яке позначимо $ F_2 $ ($ \\ overline ((A \\ vee C) \\ bigwedge B) $);

8. диз'юнкція - шукана логічна функція ($ \\ overline ((A \\ vee B) \\ bigwedge \\ overline (C)) \\ vee \\ overline ((A \\ vee C) \\ bigwedge B) $).

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

Для запису складного висловлювання у вигляді логічного виразу на формальній мові (мові алгебри логіки) в складеному висловлюванні потрібно виділити прості висловлювання і логічні зв'язки між ними.

Запишемо в формі логічного виразу складене висловлювання «(2 - 2 \u003d 5 або 2-2 \u003d 4) і (2 2 ≠ 5 або 2-2 ≠ 4) ». Проаналізуємо складене висловлювання. Воно містить два простих висловлювання:

А \u003d«2 + 2 \u003d 5» - помилково (0),

В \u003d «2 + 2 \u003d 4 \u003e\u003e - істинно (1).

Тоді складене висловлювання можна записати в такій формі:

«(А або В)і (⌐Аабо (⌐ В) ».

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

F = (A v В) & (⌐ A v ⌐ В).

Істинність або хибність складових висловлювань можна визначати чисто формально, керуючись законами алгебри висловлювань, не звертаючись до смисловому змісту висловлювань.

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

F = (AvB)&(⌐ Av⌐ B) \u003d (0v1) & (1v0) \u003d 1 & 1 \u003d 1 .

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

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

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

кількість рядків \u003d 2 n.

У нашому випадку логічна функція F = (AvB)&(⌐ Av⌐ B) має 2 змінні і, отже, кількість рядків в таблиці істинності має дорівнювати 4.

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

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

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

По-четверте, необхідно заповнити таблицю істинності за стовпцями, виконуючи базові логічні операції в необхідній послідовності і відповідно до їх таблицями істинності (табл. 4.4). Тепер ми можемо визначити значення логічної функції для будь-якого набору значень логічних змінних.

Таблиця 4.4. Таблиця істинності логічної функції

F=(AvB)&(⌐ Av⌐ B)

						(AvB) & (⌐Av⌐B)

Рівносильні логічні вирази.Логічні вирази, у яких останні стовпці таблиць істинності збігаються, називаються рівносильними.Для позначення рівносильних логічних виразів використовується знак «\u003d».

Доведемо, що логічні вирази ⌐А & ⌐Ві ⌐(AvB) рівносильні. Побудуємо спочатку таблицю істинності логічне вираження ⌐А & ⌐ В(Табл. 4.5).

Таблиця 4.5. Таблиця істинності логічного виразу ⌐А& ⌐В

				⌐А &⌐ В

Тепер побудуємо таблицю істинності логічного виразу ⌐(AvB) (Табл. 4.6).

Таблиця 4.6. Таблиця істинності логічного виразу ⌐(AvB)

			⌐(AvB)

Значення в останніх шпальтах таблиць істинності збігаються, отже, логічні вирази рівносильні:

⌐А & ⌐В \u003d ⌐ (AvB).

Вибираємо рядки, де
і виписуємо кон'юнкції всіх змінних, при чому, якщо змінна в цьому наборі дорівнює 1, то записуємо її саму, а якщо змінна \u003d 0, то її заперечення.

Для даного прикладу

конь'юнкція цих диз'юнкцій і буде шуканої формулою:

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

Число 1 особа вважається такою елементарною кон'юнкція рангу 0. Змінна вважається елементарної кон'юнкція або елементарної диз'юнкція рангу 1. Число 0 вважається елементарною диз'юнкцією рангу 0. Будь-яку кон'юнкцію змінних, яка не є тотожно хибною, можна привести до виду елементарної, а будь-яку диз'юнкцію букв, яка не є тотожно істинною , також можна привести до виду елементарної. Для цього треба застосувати властивості коммутативности, ідемпотентності і асоціативності кон'юнкції і диз'юнкції.

Строго доведено, що будь-яку формулу булевої алгебри можна виразити за допомогою операцій , &, . Інтуїтивно цей факт очевидний, згадаємо алгоритм складання формули по таблиці істинності. При цьому ми використовуємо тільки ці операції. Така форма запису називається диз'юнктивній нормальною формою(ДНФ). Це своєрідний механізм нормалізації формул алгебри логіки.

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

Аналогічно визначається КНФ - коньюктівная нормальна форма.

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

Теорема. Для будь-якої функції, що не є тотожним помилковою, існує і притому єдина СДНФ.

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

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

Системи (&, , ); (, ); (&, ), (/) - є функціонально повними

(&, ) - функціонально неповна.

Ми приймемо ці факти без докази, і вирішуючи завдання, будемо намагатися будь-яку формулу уявити за допомогою (&, , ). Пізніше ми більш детально обговоримо питання функціональної повноти і неповноти системи операцій.

Тема 1.7. Методи спрощення логічних виразів. Методи вирішення логічних завдань.

Розглянемо приклад рішення логічного завдання.

приклад :

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

Якщо поїде Арбузов, то повинні їхати Брюквин або Вишневський

Якщо поїдуть Арбузов і Вишневський то поїде Брюквин

Скласти логічну формулу прийняття рішення в символічній формі, спростити отриману формулу і сформулювати по ній нову умову формування експедиції.

Введемо змінні і відповідні їм елементарні висловлювання.

- поїде Арбузов

- поїде Брюквин

- поїде Вишневський

Тоді вироблені умови формування експедиції будуть виглядати наступним чином:

Складемо загальну формулу і спростимо вираз

тобто якщо поїде Арбузов, то поїде Брюквин.

приклад:

Якщо завтра буде хороша погода, то ми підемо на пляж або поїдемо в ліс. Складемо формулу нашої поведінки на завтра.

- хороша погода

- ми підемо на пляж

- ми поїдемо в ліс

Тепер побудуємо заперечення цієї фрази

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

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

приклад :

За підозрою в скоєнні злочину, затримані Браун, Джон і Сміт. Один з них шанована в місті старий, другий чиновник, а третій відомий шахрай. В ході слідства старий говорив правду, шахрай брехав, а третій затриманий в одному випадку говорив правду, а в іншому брехав.

Ось що вони говорили:

Браун: Я зробив це. Джон не винен. (Б & Д)

Джон: Браун не винен. Злочинець Сміт. (Б & С)

Сміт: Я не винен. Винен Браун (С & Б)

Наведемо ці висловлювання формально:

- злочин скоїв Браун

- злочин скоїв Джон

- злочин скоїв Сміт

Тоді їх слова описуються наступними виразами:

Браун:

Джон:

Сміт:

Оскільки за умовами завдання дві з цих & помилкові і одна істинна, то

Складемо таблицю істинності

Залишається тільки випадок 2, тобто злочинець Сміт, і обидва його висловлювання помилкові.

отже - помилково і - істинно

\u003d 1 - Джон шановний старий

Залишається, що Браун чиновник, і оскільки - помилково, то - істинно.

Користуючись законами і тотожністю булевої алгебри можна спрощувати логічні вирази.

приклад :

Вправа:

логічна функція - це функція, в якій змінні приймають тільки два значення: логічна одиниця або логічний нуль . Істинність або хибність складних суджень являє собою функцію істинність або хибність простих. Цю функцію називають булевої функцією суджень f (a, b) .

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

Порядок виконання логічних операцій в складному логічному вираженні:

1. інверсія;

2. кон'юнкція;

3. диз'юнкція;

4. імплікація;

5. еквівалентність.

Для зміни зазначеного порядку виконання операцій використовуються дужки.

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

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

Алгоритм побудови таблиць істинності для складних виразів:

кількість рядків \u003d 2 n + рядок для заголовка,

n - кількість простих висловлювань.

кількість стовпців \u003d кількість змінних + кількість логічних операцій;

o визначити кількість змінних (простих виразів);

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

3. Заповнити стовпці результатами виконання логічних операцій у зазначеній послідовності з урахуванням таблиць істинності основних логічних операцій.

приклад: Скласти таблицю істинності логічного виразу:

D \u003d А & (B  C).

Рішення: 

1. Визначити кількість рядків:

на вході три простих висловлювання: А, В, С тому n \u003d 3 і кількість рядків \u003d 2 3 +1 \u003d 9.

2. Визначити кількість стовпців:

o прості вирази (змінні): А, В, С ;

o проміжні результати (логічні операції):

o А - інверсія (позначимо через E );

o B  C - операція диз'юнкції (позначимо через F );

o а також шукане остаточне значення арифметичного виразу:

o D \u003d А & (B  C) . тобто D \u003d E & F - це операція кон'юнкції.

3. Заповнити стовпці з урахуванням таблиць істинності логічних операцій.

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

Правила побудови логічної функції по її таблиці істинності:

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

2. Виписати шукану формулу у вигляді диз'юнкції декількох логічних елементів. Число цих елементів дорівнює числу виділених рядків.

3. Кожен логічний елемент в цій диз'юнкції записати у вигляді кон'юнкції аргументів функції.

4. Якщо значення будь-якого аргументу функції у відповідному рядку таблиці одно 0 , То цей аргумент взяти з запереченням.

Рішення.

1. У першій і третій рядках таблиці істинності значення функції дорівнює 1 .

2. Так як рядки дві, отримуємо диз'юнкцію двох елементів: () V () .

3. Кожен логічний елемент в цій диз'юнкції Запишіть у вигляді кон'юнкції аргументів функції X і Y : (X & Y) V (X & Y) .

4. Беремо аргумент з запереченням якщо його значення у відповідному рядку таблиці одно 0 і отримуємо шукану функцію:

5. Z (X, Y) \u003d (X & Y) V (X & Y) .

Приклад 4. Визначити учасника злочину, виходячи з двох посилок:

1) "Якщо Іванов не брав участі або Петров брав участь, то Сидоров брав участь";

2) 2) "Якщо Іванов не брав участі, то Сидоров не брав участі".

Рішення

Складемо вираження:

I - "Іванов брав участь у злочині";

P - "Петров брав участь у злочині";

S - "Сидоров брав участь у злочині".

Запишемо посилки у вигляді формул:

Перевіримо результат, використовуючи таблицю істинності:

відповідь: Іванов брав участь у злочині.

Кількість вхідних змінних в заданому виразі дорівнює трьом (A, B, C). Значить, кількість вхідних наборів Q \u003d 2 3 \u003d 8.

Стовпці таблиці істинності відповідають значенням вихідних виразів A, B, C, Проміжних результатів і ( B V C), А також шуканого остаточного значення складного арифметичного виразу:

A	B	C		B V C