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

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

У логіці використовуються прості та складові логічні висловлювання (оповідальні твердження), які можуть бути істинними ( 1 ) або хибними ( 0 ).

Приклад простих висловлювань:

• "Москва - столиця Росії" (1)
• "Двічі два - три" (0)
• "Здорово!" (Не є висловлюванням)

Для поєднання кількох простих висловлювань в одне складове використовують логічні операції. Існують три базові логічні операції: І, АБО, НЕ.

Порядок операцій:

1. дії в дужках, операції порівняння (<, ≤, >, ≥, =, ≠)

Розглянемо кожну із трьох операцій окремо.

1. Операція НЕзмінює значення логічного висловлювання протилежне. Ця операція має також назви "інверсія", "логічне заперечення". Знак операції: ¬

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

2. Операція Ідля складного висловлювання дає істину лише тоді, коли істинні всі вхідні прості висловлювання. Цю операцію також можна називати як "логічне множення" або "кон'юнкція". Знак операції: , & , /\

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

3. Операція АБО для складового висловлювання дає істину тоді, коли істинно хоча б одне будь-яке вхідне просте висловлювання. "Логічна додавання", "диз'юнкція". Знак операції: + , v

Приклади розв'язання задач

приклад 1.

Для якого з наведених чисел хибний вислів:

НЕ(число > 50) АБО(число парне)?
1) 9 2) 56 3) 123 4) 8

Рішення. Спочатку виконуємо порівняння у дужках, потім операція НЕ, в останню чергу – операція АБО.

1) Підставимо число 9 у вираз:
НЕ (9 > 50) АБО(9 парне)
НЕ(брехня) АБО(брехня) = істина АБОбрехня = істина

9 нам не підходить, тому що за умовою ми маємо отримати брехню.

2) Підставимо число 56 у вираз:
НЕ (56 > 50) АБО(56 парне)
НЕ(Істина) АБО(Істина) = брехня АБОістина = істина

56 теж не підходить.

3) Підставимо 123:
НЕ (123 > 50) АБО(123 парне)
НЕ(Істина) АБО(брехня) = брехня АБОбрехня = брехня

Число 123 підійшло.

Це завдання можна було вирішити і по-іншому:
НЕ(число > 50) АБО(число парне)

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

Так як умова (число парне) має дорівнювати помилковому значенню, то відразу відкидаємо варіанти з числами 56, 8.

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

Відповідь: 3)

Приклад 2

Для якого з наведених чисел істинно висловлювання:

НЕ(Перша цифра парна) І НЕ(Остання цифра непарна)?

1) 6843 2) 4562 3) 3561 4) 1234

Спочатку виконуємо порівняння у дужках, потім операції не над дужками, в останню чергу – операція І. Все це вираз має набувати справжнього значення.

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

(Перша цифра непарна) І(Остання цифра парна) = істина

Як відомо, логічне множення І дає істину лише тоді, коли істинні усі прості висловлювання. Таким чином, обидві умови мають бути істинними:

(Перша цифра парна) = істина (Остання цифра парна) = істина

Як видно, підходить лише число 1234

Відповідь: 4)

Приклад 3

Для якого з наведених імен істинно висловлювання:
НЕ(Перша буква голосна) І(Кількість літер > 5)?

1) Іван 2) Микола 3) Семен 4) Іларіон

Перепишемо вираз:
(Перша буква не голосна)І(Кількість літер > 5) = істина
(Перша буква згодна)І(Кількість літер > 5) = істина

Тривалість уроку: 45 хв

Тип уроку:комбінований:

• перевірка знань – усна робота;
• новий матеріал – лекція;
• закріплення – практичні вправи;
• перевірка знань – завдання самостійної роботи.

Цілі уроку:

• дати поняття таблиці істинності;
• закріплення матеріалу попереднього уроку "Алгебра висловлювань";
• використання інформаційних технологій;
• прищеплення досвіду самостійного пошуку нового матеріалу;
• розвиток допитливості, ініціативи;
• виховання інформаційної культури.

План уроку:

1. Організаційний момент (2 хв).
2. Повторення матеріалу попереднього уроку (усне опитування) (4 хв).
3. Пояснення нового матеріалу (12 хв).
4. Закріплення

• аналіз прикладу (5 хв);
• практичні вправи (10 хв);
• завдання для самостійної роботи (10 хв).

Обладнання та програмний матеріал:

• біла дошка;
• мультимедійний проектор;
• комп'ютери;
• редактор презентацій MS PowerPoint 2003;
• роздатковий довідковий матеріал "Таблиці істинності";
• демонстрація презентації "Таблиці істинності".

Хід уроку

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

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

ІІ. Повторення матеріалу попереднього уроку

Давайте згадаємо основні визначення та поняття:

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

Останні два приклади належать до складних висловлювань. Як визначити істинність складних висловлювань?

Ми говорили, що вона обчислюється. І тому у логіці існують таблиці для обчислення істинності складових (складних) висловлювань. Вони називаються таблицями істинності.

Отже, тема уроку ТАБЛИЦІ ІСТИННОСТІ.

3.1) Визначення.Таблиця істинності – це таблиця, що показує істинність складного висловлювання за всіх можливих значеннях вхідних змінних (Малюнок 1).

3.2) Розберемо докладніше кожну логічну операцію відповідно до її визначення:

1. Інверсія (заперечення) – це логічна операція, яка кожному простому висловлюванню ставить у відповідність складове висловлювання, у тому, що вихідне висловлювання заперечується.

Ця операція відноситься лише до однієї змінної, тому для неї відведено лише двірядки, т.к. одна змінна може мати одне з двохзначень: 0 чи 1.

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

Легко побачити, що дана таблиця справді схожа таблицю множення.

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

Можна переконатися, що таблиця схожа на таблицю складання останньої дії. У двійковій системі числення 1 + 1 = 10, у десятковій – 1 + 1 = 2. У логіці значення змінної 2 неможливо, розглянемо 10 з погляду логіки: 1 – істинно, 0 – хибно, т.ч. 10 – істинно і хибно одночасно, чого не може, тому остання дія суворо спирається визначення.

4. Імплікація (слідування) – це логічна операція, що ставить у відповідність кожним двом простим висловлюванням складне висловлювання, що є хибним тоді і тільки тоді, коли умова істинна, а слідство хибне.

5. Еквіваленція (рівносильність) – це логічна операція, що ставить у відповідність кожним двом простим висловлюванням складне висловлювання, що є істинним тоді і тільки тоді, коли обидва вихідні висловлювання одночасно істинні чи хибні.

Останні дві операції було розібрано нами на попередньому уроці.

3.3) Розберемо алгоритм складання таблиці істинностідля складного висловлювання:

3.4) Розглянемо приклад складання таблиці істинності для складного висловлювання:

приклад. Побудувати таблицю істинності для формули: А U В -> ¬ А U С.

Рішення (Малюнок 2)

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

IV. Закріплення.

Для закріплення матеріалу вам пропонується вирішити самостійно приклади під літерами а, б, в додатково г-ж (Малюнок 3).

V. Домашнє завдання, узагальнення матеріалу.

Домашнє завдання дано вам також на моніторі (Малюнок 4)

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

Алгебра логіки

Алгебра логіки

Алгебра логіки(англ. algebra of logic) - один із основних розділів математичної логіки, в якому методи алгебри використовуються в логічних перетвореннях.

Основоположником алгебри логіки є англійський математик і логік Дж. Буль (1815-1864), який поклав основою свого логічного вчення аналогію між алгеброю і логікою. Будь-яке висловлювання він записував за допомогою символів розробленої ним мови та отримував «рівняння», істинність чи хибність яких можна було довести, виходячи з певних логічних законів, таких як закони комутативності, дистрибутивності, асоціативності та ін.

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

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

Наприклад, «3 помножити на 3 і 9», «Архангельськ на північ від Вологди» — справжні висловлювання, а «П'ять менше трьох», «Марс — зірка» — хибні.

Очевидно, що не всяка пропозиція може бути логічним висловлюванням, тому що не завжди є сенс говорити про його хибність чи істинність. Наприклад, вислів «Інформатика – цікавий предмет» невизначений і вимагає додаткових відомостей, а вислів «Для учня 10-А класу Іванова А. А. інформатика – цікавий предмет» залежно від інтересів Іванова А. А. може набувати значення «істина» або «брехня».

Крім двозначної алгебри висловлювань, в якій приймаються тільки два значення - "істинно" і "хибно", існує багатозначна алгебра висловлювань.У такій алгебрі, крім значень «істинно» і «хибно», вживаються такі істинні значення, як «ймовірно», «можливо», «неможливо» тощо.

У алгебрі логіки різняться прості(елементарні) висловлювання, що позначаються латинськими літерами (A, B, C, D, …), та складні(складові), складені з кількох простих за допомогою логічних зв'язок, наприклад, таких, як "ні", "і", "або", "тоді і тільки тоді", "якщо ... то". Істинність чи хибність одержуваних таким чином складних висловлювань визначається значенням простих висловлювань.

Позначимо як Авислів «Алгебра логіки успішно застосовується в теорії електричних схем», а через У- "Алгебра логіки застосовується при синтезі релейно-контактних схем".

Тоді складний вислів «Алгебра логіки успішно застосовується в теорії електричних ланцюгіві при синтезі релейно-контактних схем» можна коротко записати як А і В; тут "і" - логічна зв'язка. Очевидно, що оскільки елементарні висловлювання А і Вістинні, то істинно і складне висловлювання А і В.

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

Логічних значень всього два: істина (TRUE)і брехня (FALSE). Це відповідає цифровому уявленню. 1 і 0 . Результати кожної логічної операції можна записати як таблиці. Такі таблиці називають таблицями істинності.

Основні операції алгебри логіки

1. Логічне заперечення, інверсія(Лат. inversion- перевертання) - логічна операція, в результаті якої з цього висловлювання (наприклад, А) виходить нове висловлювання ( не А), яке називається запереченням вихідного висловлювання, позначається символічно рисою зверху ($A↖(-)$) або такими умовними позначеннями, як ¬, "not", і читається: "не А", "А хибно", "невірно, що А", "заперечення А". Наприклад, «Марс – планета Сонячна система»(висловлювання А); "Марс - не планета Сонячної системи" ($A↖(-)$); вислів «10 - просте число» (висловлювання В) хибно; вислів "10 - не просте число" (висловлювання B) істинно.

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

Вислів $A↖(-)$ хибно, коли А істинно, і істинно, коли А хибно.

Геометрично заперечення можна так: якщо А — це кілька точок, то $A↖(-)$ — це доповнення безлічі А, т. е. всі точки, які належать безлічі А.

2.Кон'юнкція(Лат. conjunctio- з'єднання) - логічне множення, операція, що вимагає як мінімум двох логічних величин (операндів) і що з'єднує два або більше висловлювань за допомогою зв'язки «і»(наприклад, «А та В»), яка символічно позначається за допомогою знака ∧ (А ∧ В) та читається: «А та В». Для позначення кон'юнкції застосовуються такі знаки: А ∙ В; А & В, А and В, інколи ж між висловлюваннями не ставиться ніякого знака: АВ. Приклад логічного множення: Цей трикутник рівнобедрений і прямокутний. Даний вислів може бути істинним тільки в тому випадку, якщо виконуються обидві умови, інакше висловлювання є хибним.

Висловлювання А ∧ Уістинно тільки тоді, коли обидва висловлювання Аі Уістинні.

Геометрично кон'юнкцію можна представити так: якщо А, В А ∧ Ує перетин множин Аі У.

3. Диз'юнкція(Лат. disjunction- Поділ) - логічне додавання, операція, що з'єднує два або більше висловлювань за допомогою зв'язки «або»(наприклад, «А чи В»), яка символічно позначається за допомогою знака ∨ (А∨ в)і читається: «А чи В». Для позначення диз'юнкції застосовуються такі знаки: А+В; А або В; А | B. Приклад логічного складання: «Кількість x ділиться на 3 чи 5». Цей вислів буде істинним, якщо виконуються обидві умови або хоча б одна з умов.

Таблиця істинності операції має вигляд

Висловлювання А∨ Ухибно тільки тоді, коли обидва висловлювання Аі Ухибні.

Геометрично логічне додавання можна подати так: якщо А, В- це деякі безлічі точок, то А ∨ У- це об'єднання множин Аі У, Т. е. фігура, що поєднує і квадрат, і коло.

4. Диз'юнкція строго-розділювальна, додавання по модулю два- логічна операція, що з'єднує два висловлювання за допомогою зв'язки «або», ужитої у винятковому сенсі, яка символічно позначається за допомогою знаків ∨ ∨ або ⊕ ( А ∨ ∨ В, А ⊕ У) і читається: "або А, або В". Приклад додавання по модулю два – вислів «Цей трикутник тупокутний або гострокутний». Вислів істинний, якщо виконується якась одна з умов.

Таблиця істинності операції має вигляд

Висловлювання А ⊕ В істинно лише тоді, коли висловлювання А та В мають різні значення.

5. Імплікація(Лат. implisito- тісно пов'язую) - логічна операція, що з'єднує два висловлювання за допомогою зв'язки "якщо то"у складне висловлювання, яке символічно позначається за допомогою знака → ( А → У) і читається: «якщо А, то», «А тягне», «з А випливає», «А імплікує». Для позначення імплікації також застосовується знак ⊃ (A ⊃ B). Приклад імплікації: «Якщо отриманий чотирикутник квадрат, то біля нього можна описати коло». Ця операція пов'язує два простих логічних вирази, у тому числі перше є умовою, а друге — наслідком. Результат операції покладено лише тоді, коли передумова є істина, а наслідок – брехня. Наприклад, «Якщо 3 * 3 = 9 (А), то Сонце – планета (В)», результат імплікації А → В – брехня.

Таблиця істинності операції має вигляд

Для операції імплікації справедливе твердження, що з брехні може випливати що завгодно, та якщо з істини — лише істина.

6. Еквівалентність, подвійна імплікація, рівнозначність(Лат. aequalis- рівний і valentis- що має силу) - логічна операція, що дозволяє з двох висловлювань Аі Уотримати новий вислів А ≡ В, яке читається: "А еквівалентно B". Для позначення еквівалентності застосовуються також такі знаки: ⇔, ∼. Ця операція може бути виражена зв'язками «тоді й тільки тоді», «необхідно і достатньо», «рівносильно». Прикладом еквівалентності є вислів: «Трикутник буде прямокутним тоді і лише тоді, коли один із кутів дорівнює 90 градусам».

Таблиця істинності операції еквівалентності має вигляд

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

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

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

За допомогою логічних змінних та логічних операцій будь-який логічний вислів можна формалізувати, тобто замінити логічною формулою. При цьому елементарні висловлювання, що утворюють складове висловлювання, можуть бути абсолютно не пов'язані за змістом, але це не заважає визначати істинність чи хибність складеного висловлювання. Наприклад, вислів «Якщо п'ять більше двох ( А), то вівторок завжди настає після понеділка ( У)» - імплікація А→ У, і результат операції в даному випадку – «істина». У логічних операціях сенс висловлювань не враховується, розглядається лише їхня істинність чи хибність.

Розглянемо, наприклад, побудову складного висловлювання з висловлювань Аі У, яке було б хибним тоді і тільки тоді, коли обидва висловлювання істинні. У таблиці істинності для операції додавання по модулю знаходимо: 1 ⊕ 1 = 0. А висловлювання може бути, наприклад, таким: «Цей м'яч повністю червоний або повністю синій». Отже, якщо затвердження А"Цей м'яч повністю червоний" - істина, і твердження У"Цей м'яч повністю синій" - істина, то складне твердження - брехня, тому що одночасно і червоним, і синім м'яч бути не може.

Приклади розв'язання задач

приклад 1.Визначити для вказаних значень X значення логічного висловлювання ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

Звідси отримуємо:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

приклад 2.Вказати безліч цілих значень X, для яких істинно вираз ((X > 2) → (X > 5)) .

Рішення.Операція заперечення застосована до всього виразу ((X > 2) → (X > 5)), отже, коли вираз ¬((X > 2) → (X > 5)) істинно, вираз ((X > 2) →(X > 5)) хибно. Тому необхідно визначити, для яких значень X вираз ((X > 2) → (X > 5)) є хибним. Операція імплікації набуває значення «брехня» тільки в одному випадку: коли з істини випливає брехня. І це виконується лише X = 3; X = 4; X = 5.

приклад 3.Для яких із наведених слів хибне висловлювання (перша буква голосна ∧ третя буква голосна) ⇔ рядок з 4 символів? 1) асса; 2) куку; 3) кукурудза; 4) помилка; 5) силач.

Рішення.Розглянемо послідовно всі запропоновані слова:

1) для слова асса отримаємо: ¬ (1 ∧ 0) ⇔ 1, 1 ⇔ 1 - висловлювання істинно;

2) для слова куку отримаємо: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - висловлювання істинно;

3) для слова кукурудза отримаємо: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - висловлювання хибно;

4) для слова помилка отримаємо: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - висловлення істинно;

5) для слова силач отримаємо: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — висловлювання хибне.

Логічні висловлювання та їх перетворення

Під логічним виразомслід розуміти такий запис, який може набувати логічного значення «істина» чи «брехня». При такому визначенні серед логічних виразів слід розрізняти:

• вирази, які використовують операції порівняння («більше», «менше», «рівно», «не дорівнює» тощо) і набувають логічних значень (наприклад, вираз а > b , де а = 5 і b = 7, дорівнює значенню «брехня»);
• безпосередні логічні вирази, пов'язані з логічними величинами та логічними операціями (наприклад, A ∨ В ∧ С, де А = істина, B = брехня та C = істина).

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

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

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

приклад.Знайти значення виразу:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ для а = 2, b = 3, A = істина, В = брехня.

Рішення.Порядок підрахунку значень:

1) b a + a b > a + b, після підстановки отримаємо: 3 2 + 2 3 > 2 + 3, тобто 17 > 2 + 3 = істина;

2) A ∧ B = істина ∧ брехня = брехня.

Отже, вираз у дужках дорівнює (b a + a b > a + b ∨ A ∧ B) = істина ∨ брехня = істина;

3) 1 ≤ a = 1 ≤ 2 = істина;

4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

Після цих обчислень одержимо остаточно: істина ∨ А ∧ істина ∧ ¬В ∧ ¬істина.

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

5) ¬В = ¬брехня = істина; ¬істина = брехня;

6) A ∧ істина ∧ істина ∧ брехня = істина ∧ істина ∧ істина ∧ брехня = брехня;

7) істина ∨ брехня = істина.

Таким чином, результат логічного вираження при заданих значеннях - "Істина".

Примітка.Враховуючи, що вихідне вираз є, зрештою, сума двох доданків, і значення одного з них 1 ≤ a = 1 ≤ 2 = істина, без подальших обчислень можна сказати, що результат для всього виразу теж «істина».

Тотожні перетворення логічних виразів

В алгебрі логіки виконуються основні закони, що дозволяють робити тотожні перетворення логічних виразів.

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

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

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

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

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

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

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Тут спрощення застосовується закон поглинання.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

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

Приклади розв'язання задач

приклад 1.Знайти логічний вираз, рівносильний виразу A ∧ ¬(¬B ∨ C) .

Рішення.Застосовуємо правило де Моргана для і С: ¬(¬B ∨ C) = B ∧ ¬C .

Отримуємо вираз, рівносильний вихідному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Відповідь: A ∧ B ∧ ¬C.

приклад 2.Вказати значення логічних змінних А, В, С, для яких значення логічного виразу (A ∨ B) → (B ∨ C ∨ B) хибно.

Рішення.Операція імплікації хибна тільки у випадку, коли з істинної посилки слід брехня. Отже, для заданого виразу посилка A ∨ B повинна набувати значення «істина», а наслідок, тобто вираз B ∨ C ∨ B , - «брехня».

1) A ∨ B – результат диз'юнкції – «істина», якщо хоча б один із операндів – «істина»;

2) B ∨ ¬C ∨ B — вираз хибно, якщо всі доданки мають значення «брехня», тобто В — «брехня»; ¬C — «брехня», а отже, змінна має значення «істина»;

3) якщо розглянути посилку і врахувати, що В - "брехня", то отримаємо, що значення А - "істина".

Відповідь:А – істина, В – брехня, С – істина.

приклад 3.Яке найбільше ціле число X, за якого істинно висловлювання (35

Рішення.Запишемо таблицю істинності для операції імплікації:

Вираз X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Відповідь: X = 5.

Використання логічних виразів для опису геометричних областей

Логічні вирази можуть бути використані для опису геометричних областей. В цьому випадку завдання формулюється так: записати для заданої геометричної області такий логічний вираз, який набуває значення «істина» для значень x, y тоді і тільки тоді, коли будь-яка точка з координатами (x; y) належить геометричній області.

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

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

1) .

Рішення.Задану геометричну область можна представити у вигляді набору наступних областей: перша область — D1 — напівплощина $(x)/(-1) +(y)/(1) ≤ 1$, друга — D2 — коло з центром на початку координат $x ^2 + y^2 ≤ 1$. Їх перетин D1 $∩$ D2 є шуканою областю.

Результат:логічний вираз $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Цю область можна записати так: | ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

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

Можна вирішити обернену задачу, а саме: намалювати область для заданого логічного вираження.

приклад 2.Намалювати та заштрихувати область, для точок якої виконується логічна умова y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Рішення.Шукана область являє собою перетин трьох напівплощин. Будуємо на площині (x, y) прямі y = x; y = -x; y = 2. Це межі області, причому остання межа y = 2 не належить області, тому її наносимо пунктирною лінією. Для виконання нерівності y ≥ x потрібно, щоб точки знаходилися ліворуч від прямої y = x, а нерівність y = -x виконується для точок, що знаходяться праворуч від прямої y = -x. Умова y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Використання логічних функцій для опису електричних схем

Логічні функції дуже зручні описи роботи електричних схем. Так, для схеми, представленої на рис., де значення змінної X - це стан вимикача (якщо він включений, значення X - "істина", а якщо вимкнений - "брехня"), це значення Y - це стан лампочки (якщо вона горить - Значення "істина", а якщо ні - "брехня"), логічна функція запишеться так: Y = X . Функцію Y називають функцією провідності.

Для схеми, представленої на рис., логічна функція Y має вигляд: Y = X1 ∪ X2, тому що достатньо одного включеного вимикача, щоб горіла лампочка. У схемі на рис., щоб горіла лампочка, повинні бути включені обидва вимикачі, отже, функція провідності має вигляд: Y = X1 ∧ X2 .

Для більш складної схеми функція провідності матиме вигляд: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

Використання апарату алгебри логіки під час проектування логічних схем

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

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

Технічно комп'ютерний логічний елемент реалізується як електричної схеми, Що являє собою з'єднання різних деталей: діодів, транзисторів, резисторів, конденсаторів. На вхід логічного елемента, який називають також вентилем, надходять електричні сигнали високого та низького рівнів напруги, на вихід видається один вихідний сигнал або високого, або низького рівня. Ці рівні відповідають одному зі станів двійкової системи: 1 - 0; ІСТИНА - БРЕХНЯ. Кожен логічний елемент має своє умовне позначення, яке виражає його логічну функцію, але не вказує на те, яка саме електронна схемау ньому реалізована. Це спрощує запис та розуміння складних логічних схем. Роботу логічних схем описують з допомогою таблиць істинності. Умовне позначенняна схемі АБО знак "1" - від застарілого позначення диз'юнкції як "> = 1" (значення диз'юнкції дорівнює 1, якщо сума двох операндів більше або дорівнює 1). Знак & на схемі І є скороченим записом англійського слова and.

З логічних елементів складаються електронні логічні схеми, що виконують складніші логічні операції. Набір логічних елементів, що складається з елементів НЕ, АБО, І, за допомогою яких можна побудувати логічну структуру будь-якої складності, називається функціонально повним.

Побудова таблиць істинності логічних виразів

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

Зручною формою запису під час знаходження значень функції є таблиця, що містить, крім значень змінних і значень функції, також значення проміжних обчислень. Розглянемо приклад побудови таблиці істинності для формули $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

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

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

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

Алгоритм побудови ДНФ наступний:

1. у таблиці істинності функції вибирають набори аргументів, котрим логічні форми рівні 1 («істина»);
2. всі вибрані логічні набори як логічні твори аргументів записують, послідовно з'єднавши їх між собою операцією логічної суми (диз'юнкції);
3. для аргументів, які є хибними, у побудованому записі проставляють операцію заперечення.

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

Рішення.Вибираємо набори значень аргументів, у яких функція дорівнює 1. Це перший і четвертий рядки таблиці (рядок заголовка при нумерації не враховуємо).

Записуємо логічні твори аргументів цих наборів, об'єднавши їх логічною сумою: X1 ∧ X2 ∨ X1 ∧ X2 .

Записуємо заперечення щодо аргументів вибраних наборів, що мають хибне значення (четвертий рядок таблиці; другий набір у формулі; перший і другий елементи): X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Відповідь: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

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

Алгоритм побудови КНФ наступний:

1. у таблиці істинності вибирають набори аргументів, котрим логічні форми рівні 0 («брехня»);
2. всі вибрані логічні набори як логічні суми аргументів записують послідовно, поєднавши їх між собою операцією логічного твору (кон'юнкції);
3. для аргументів, які є істинними, у побудованому записі проставляють операцію заперечення.

Приклади розв'язання задач

приклад 1.Розглянемо попередній приклад, тобто побудуємо функцію, що визначає, що перше число дорівнює другому, використовуючи метод КНФ. Для заданої функції її таблиця істинності має вигляд

Рішення.Вибираємо набори значень аргументів, у яких функція дорівнює 0. Це другий і третій рядки (рядок заголовка при нумерації не враховуємо).

Записуємо логічні суми аргументів цих наборів, об'єднавши їх логічним твором: X1 ∨ X2 ∧ X1 ∨ X2 .

Записуємо заперечення щодо аргументів вибраних наборів, що мають справжнє значення (другий рядок таблиці, перший набір формули, другий елемент; для третього рядка, а це другий набір формули, перший елемент): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Таким чином, отримано запис логічної функції у КНФ.

Відповідь: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

Отримані двома методами значення функцій є еквівалентними. Для доказу цього твердження використовуємо правила логіки: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖(-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2)↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Приклад 2. Побудувати логічну функцію для заданої таблиці істинності:

Шукана формула: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

Її можна спростити: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

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

Шукана формула: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-$) (X3)↖(-)$.

Формула досить громіздка, і її слід спростити:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Таблиці істинності на вирішення логічних завдань

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

Приклади розв'язання задач

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

Рішення.Очевидно, що результатом рішення буде таблиця, в якій функція Y(X1, X2, X3) буде мати значення «істина», якщо які-небудь дві змінні мають значення «істина».

приклад 2.Скласти розклад уроків щодня, враховуючи, що урок інформатики може лише першим чи другим, урок математики — першим чи третім, а фізики — другим чи третім. Чи можливо скласти розклад, задовольнивши всі вимоги? Скільки існує варіантів розкладу?

Рішення.Завдання легко вирішується, якщо скласти відповідну таблицю:

З таблиці видно, що є два варіанти шуканого розкладу:

1. математика, інформатика, фізика;
2. інформатика, фізика, математика.

приклад 3.До спортивного табору приїхали троє друзів — Петро, ​​Борис та Олексій. Кожен із них захоплюється двома видами спорту. Відомо, що таких видів спорту є шість: футбол, хокей, лижі, плавання, теніс, бадмінтон. Також відомо, що:

1. Борис - найстарший;
2. що грає у футбол молодше грає у хокей;
3. граючі у футбол і хокей та Петро живуть в одному будинку;
4. коли між лижником та тенісистом виникає сварка, Борис мирить їх;
5. Петро не вміє грати ні теніс, ні бадмінтон.

Якими видами спорту захоплюється кожен із хлопчиків?

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

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

З умови 4 випливає, що Борис не захоплюється ні лижами, ні тенісом, а з умов 3 і 5, що Петро не вміє грати у футбол, хокей, теніс та бадмінтон. Отже, улюблені види спорту Петра – лижі та плавання. Занесемо це в таблицю, а клітинки стовпців «Лижі» і «Плавання», що залишилися, заповнимо нулями.

З таблиці видно, що у теніс може грати лише Олексій.

З умов 1 та 2 випливає, що Борис не футболіст. Таким чином у футбол грає Олексій. Продовжимо заповнювати таблицю. Внесемо до порожні осередкирядки «Олексій» нулі.

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

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

Урок інформатики 9 клас

Тема: Поняття, судження, висновок. Поняття «істина» та «брехня».

Тема: Поняття «істина» та «брехня»

Цілі:

познайомити учнів з поняттями «справжнє та хибне висловлювання»;

вчити визначати, чи висловлювання є істинним з погляду об'єктивної дійсності;

Педагогічні завдання уроку:

розвивати логічне мислення, спостережливість, мовлення;

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

Вимоги до рівня освоєння навчального матеріалу після завершення уроку:

знати, як люди здобувають «істину»;

вміти оцінювати істинність і виправляти його, якщо воно хибне;

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

Ключові поняття:поняття «істина», «брехня».

Характеристика уроку:

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

тип уроку: комбінований (формування нових знань на основі актуалізації наявного життєвого досвіду та знань);

стратегія: аналіз наявних знань із виходом новий рівень осмислення істинних і хибних висловлювань.

Матеріальне забезпечення уроку: підручник, демонстраційний ПК.

Зразковий план уроку:

Організаційний момент (1-2 хв).

Вивчення нової теми (10-12)

Первинне закріплення (9-12 хв).

Фізкультхвилинка (2-3 хв).

Комп'ютерний практикум (10-12 хв).

Узагальнення та підбиття підсумків (3 хв).

Коментар вчителя до домашнього завдання(2-3 хв).

Хід уроку

Організація учнів працювати.

Девіз уроку: «Вважай нещасним той день і ту годину, коли ти не засвоїв нічого нового, нічого не додав до своєї освіти».

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

II. Вивчення нової теми

Підготовча робота.

Гра «Істина – брехня»

Підберіть синонім до слова "правда", а тепер до слова "неправда".

Нові знання буде важко здобувати і освоювати без уміння швидко і правильно відповідати на поставлені питання, тому почнемо урок з гри «Істина – брехня»

Я висловлюватиму деякі думки, якщо ви вірите мені, то підніміть картку «І», якщо ні, то картку «Л».

Усі крокодили літають.

Комп'ютер – помічник людини під час рахунку.

10 ділиться на 3 без залишку.

Телефон є засобом зв'язку.

Наша школа знаходиться у 29 мікрорайоні.

Нині у нас не урок інформатики.

Місто Темрюе – столиця Краснодарського краю.

У місті всі школи чотириповерхові.

Ви учні 4-ої школи та четверокласники.

Введення понять «хибне, справжнє висловлювання»

Назвіть висловлювання, яким ви повірили. Чому? (Бо це відповідає дійсності, це правда)

Такі висловлювання називаються істиннимитобто правдивими, відповідними дійсності.

Як можна назвати висловлювання, які ви вважали невірними?

Такі висловлювання є хибними.

Запам'ятай! Істина - це те, що відповідає дійсності.

Брехня – те, що насправді не відповідає.

Закріплення матеріалу.

Гра "Хто більше?"

Щоб перевірити, наскільки ви зрозуміли новий матеріал, я пропоную вам гру-змагання «Хто більше?»

Правила гри наступні: клас ділиться на дві команди «Істина» та «Брехня». Відповідно хлопці з команди «Істина» наводять приклади справжніх висловлювань, а хлопці з команди «Брехня» хибних висловлювань.

Молодці! Ви чудово впоралися із завданням. Як ви вважаєте, чому в нашому змаганні немає переможців і переможених?

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

2) Робота за підручником.

Читання підручника стор. 82-85

Фронтальне опитування.

Чи завжди легко визначити, коли те чи інше висловлювання є істинним? (ні, іноді не вистачає знань та досвіду)

Які дії має зробити людина, щоб здобути істину? (спостерігати, порівнювати, розмірковувати, обчислювати, вимірювати, проводити дослідження)

Що є результатом роздумів? (усне висловлювання чи висловлювання як тексту, малюнка, числа, схеми, формулы)

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

Фізмінутка.

Гра «Роби навпаки»

Урок ми розпочали з підбору синонімів, а зараз я пропоную вам підібрати антоніми, причому усно.

Я вимовлятиму висловлювання-дії, а ви робитимете все навпаки.

Сидіть.

Чи не стрибайте.

Чи не стійте.

Не піднімайте руки.

Плачте.

Не тупайте.

Мовчіть.

Чи не присідайте.

Не сідайте.

Чи не слухайте.

Робота у зошитах.

№ 1. Встав пропущені слова:

Поняття «істина» та « брехня »- це несумісні поняття.

Істина не завжди лежить на поверхні.

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

Висловлювання може бути істинним або хибним .

Істина – це те, що відповідає насправді.

Брехня – те, що насправді не відповідає.

№ 5. Оброби графічну та текстову інформацію та вкажи справжні ці міркування або помилкові, виділивши потрібну букву.

№ 6. а) Розглянь схему.

«дерево»

«Клен»

«ялина»

«сосна»

«дуб»

Придумай позначення слів та заповни діаграму

Сьогодні ми поговоримо про предмет під назвою інформатики. Таблиця істинності, різновиду функцій, порядок їх виконання – це наші основні питання, на які ми намагатимемося знайти відповіді у статті.

Зазвичай цей курс викладається ще в середній школі, але велика кількість учнів є причиною нерозуміння деяких особливостей. А якщо ви зібралися присвятити цьому своє життя, то просто не обійтися без складання єдиного державного іспиту з інформатики. Таблиця істинності, перетворення складних виразів, вирішення логічних завдань – це все може зустрітися у квитку. Зараз ми розглянемо докладніше цю тему і допоможемо вам набрати більше балів на ЄДІ.

Предмет логіки

Що ж це за предмет – інформатика? Таблиця істинності – як її будувати? Для чого потрібна наука логіка? На всі ці запитання ми зараз із вами відповімо.

Інформатика – це досить цікавий предмет. Він не може викликати труднощі у сучасного суспільстваАдже все, що нас оточує, так чи інакше, відноситься до комп'ютера.

Основи науки логіки даються викладачами середньої школи під час уроків інформатики. Таблиці істинності, функції, спрощення виразів – усе це мають пояснювати вчителі інформатики. Ця наука просто потрібна в нашому житті. Придивіться, все підкоряється будь-яким законам. Ви підкинули м'яч, він підлетів вгору, але після цього знову впав на землю, це сталося через наявність законів фізики та сили земного тяжіння. Мама варить суп та додає сіль. Чому коли ми його їмо, нам не трапляються крупинки? Все просто, сіль розчинилася у воді, підкоряючись законам хімії.

Тепер зверніть увагу на те, як ви розмовляєте.

• "Якщо я відвезу свого кота до ветеринарної клініки, то йому зроблять щеплення".
• "Сьогодні був дуже важкий день, бо приходила перевірка".
• «Я не хочу йти до університету, бо сьогодні буде колоквіум» і таке інше.

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

Функції

Щоб скласти таблицю істинності до запропонованої вам задачі, необхідно знати логічні функції. Що це таке? Логічна функція має деякі змінні, які є твердженнями (справжніми чи хибними), і саме значення функції має дати нам відповідь на запитання: «Вираз істинно чи хибно?».

Усі вирази приймають такі значення:

• Істина чи брехня.
• І чи Л.
• 1 чи 0.
• Плюс чи мінус.

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

Всього в логіці виділяють сім функцій або зв'язків, що поєднують вирази:

• Множення (кон'юнкція).
• Додавання (диз'юнкція).
• Наслідок (імплікація).
• Еквівалентність.
• Інверсія
• Штрих Шеффера.
• Стрілка Пірса.

Перша операція, подана у списку, має назву «логічне множення». Її графічно можна назвати як перевернутої галочки, знаками & чи *. Друга в нашому списку операція - логічне додавання, що графічно позначається у вигляді галочки, +. Імплікацію називають логічним наслідком, що позначається у вигляді стрілки, що вказує від умови на слідство. Еквіваленція позначається двосторонньою стрілкою, функція має справжнє значення тільки в тих випадках, коли обидва значення набувають або значення «1», або «0». Інверсію називають логічним запереченням. Штрих Шеффера називають функцією, яка заперечує кон'юнкцію, а стрілку Пірса – функцією, що заперечує диз'юнкцію.

Основні двійкові функції

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

Кон'юнкція (множення). Якщо два в результаті ми отримуємо істину, у всіх інших випадках ми отримуємо брехню.

Результат - брехня при логічному складанні ми маємо лише у разі двох помилкових вхідних даних.

Логічне слідство має хибний результат лише тоді, коли умова є істиною, а слідство – неправдою. Тут можна навести приклад із життя: "Я хотів купити цукор, але магазин був закритий", отже, цукор так і не куплений.

Еквіваленція є істиною лише у випадках однакових значень вхідних даних. Тобто при парах: "0; 0" або "1; 1".

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

Штрих Шиффера буде на виході мати хибний результат лише за наявності двох справжніх виразів.

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

В якому порядку виконувати логічні операції

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

• логічне заперечення;
• множення;
• додавання;
• слідство;
• еквівалентність;
• заперечення множення (штрих Шеффера);
• заперечення додавання (стрілка Пірса).

Приклад №1

Зараз ми пропонуємо розглянути приклад побудови таблиці істинності для 4 змінних. Необхідно дізнатися у яких випадках F=0 у рівняння: неА+В+С*D

Відповіддю це завдання буде перерахування наступних комбінацій: «1;0;0;0», «1;0;0;1» і «1;0;1;0». Як бачите, складати таблицю істинності досить легко. Ще раз хочеться звернути вашу увагу на порядок виконання дій. У конкретному випадку він був наступним:

1. Інверсія першого простого вираження.
2. Кон'юнкція третього та четвертого виразу.
3. Диз'юнкція другого виразу з результатами попередніх обчислень.

Приклад №2

Зараз ми розглянемо ще одне завдання, яке потребує побудови таблиці істинності. Інформатика (приклади були взяті зі шкільного курсу) може мати і завдання. Коротко розглянемо одну із них. Чи винен Ваня в крадіжці м'яча, якщо відомо таке:

• Якщо Ваня не крав чи Петя крав, то Сергій взяв участь у крадіжці.
• Якщо Ваня не винен, то і Сергій м'яч не крав.

Введемо позначення: І – Ваня вкрав м'яч; П – Петя вкрав; С – Сергій вкрав.

За цією умовою ми можемо скласти рівняння: F=((неІ+П) імплікація С)*(неІ імплікація неС). Нам потрібні ті варіанти, де функція набуває справжнього значення. Далі потрібно скласти таблицю, оскільки дана функція має цілих 7 процесів, ми їх опустимо. Вноситимемо лише вхідні дані та результат.

Зверніть увагу на те, що в цій задачі ми замість знаків «0» і «1» використовували плюс і мінус. Це також прийнятно. Нас цікавлять комбінації, де F = +. Проаналізувавши їх, ми можемо зробити наступний висновок: Ваня брав участь у крадіжці м'яча, тому що у всіх випадках, де F набуває значення +, І має позитивне значення.

Приклад №3

Наразі пропонуємо вам знайти кількість комбінацій, коли F=1. Рівняння має такий вигляд: F = неА + В * А + не. Складаємо таблицю істинності:

Відповідь: 4 комбінації.