теорема поглинання записується в двох формах - диз'юнктивній і

кон'юнктівной, відповідно:

А + АВ \u003d А (16)

А (А + В) \u003d А (17)

Доведемо першу теорему. Винесемо за дужки букву А:

А + АВ \u003d А (1 + В)

Згідно з теоремою (3) 1 + В \u003d 1, отже

А (1 + В) \u003d А 1 \u003d А

Щоб довести другу теорему, розкриємо дужки:

А (А + В) \u003d А А + АВ \u003d А + АВ

Вийшло вираз, тільки що доведене.

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

спрощення булевих формул.

теорема склеювання також має дві форми - діз'юнктівную і

кон'юнктівную:

Доведемо першу теорему:

оскільки згідно теорем (5) і (4)

Для доказу другої теореми розкриємо дужки:

Згідно з теоремою (6) отже:

По теоремі поглинання (16) А + АВ \u003d А

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

булевих формул, наприклад:

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

Диз'юнкцію, кон'юнкцію і інверсію:

Перша теорема читається так: інверсія кон'юнкції є диз'юнкція

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

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

лекція 5

Інвертування складних виразів

Теорема де Моргана застосовна не тільки до окремих кон'юнкції

або диз'юнкції, а й до більш складним виразами.

Знайдемо інверсію вираження АВ + CD , представленого у вигляді диз'юнкції кон'юнкція. Інвертування будемо вважати закінченим, якщо знаки заперечення стоять тільки над змінними. Введемо позначення: АВ \u003d Х;

CD \u003d Y,тоді

Знайдемо і підставимо в вираз (22):

Таким чином:

Розглянемо вираз, представлене в кон'юнктівной формі:

(А + В) (С + D)

Знайдемо його інверсію у вигляді

Введемо позначення: А + В \u003d X; З + D \u003d Y,тоді

Знайдемо і підставимо їх у вираз

Таким чином:

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

Поняття булевої функції

Взагальному випадку функція (лат. functio - виконання, відповідність,

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

під яким розуміється область значень залежного змінного f . У разі булевих функцій X \u003d F \u003d (0,1). Правилом, за допомогою якого задається функція, може служити будь-яка булева формула, наприклад:

символом f тут позначена функція, яка є, як і аргументи А, В, С,двійковій змінної.

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

Головна особливість функції: щоб визначити її значення, в загальному випадку необхідно знати значення всіх аргументів, від яких вона залежить. Наприклад, наведена вище функція залежить від трьох аргументів А, В, С.Якщо прийняти А \u003d 1, то отримаємо

т. е. вийшло нове вираз, що не дорівнює ні нулю, ні

одиниці. нехай тепер В\u003d 1. Тоді

т. е. і в цьому випадку невідомо, чому дорівнює функція, нулю або одиниці.

Приймемо, нарешті, З\u003d 0. Тоді отримаємо: f = 0. Таким чином, якщо в вихідному виразі прийняти А \u003d 1, В= 1, З = 0, то функція прийме нульове значення: f \u003d 0.

Розглянемо поняття набору значень змінних .

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

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

Наприклад, якщо

то згідно латинському алфавіту першим є аргумент Р, другим -

Q,третім - X, четвертим - У. Тоді по набору значень аргументів легко

знайти значення функції. Нехай, наприклад, дано набір 1001. Згідно з його

записи т. е. на наборі 1001 задана функція дорівнює одиниці.

Ще раз відзначимо, що набір значень аргументів - це сукупність

нулів і одиниць. Двійкові числа також є наборами нулів і одиниць.

Звідси виникає питання - чи не можна набори розглядати як двійкові

числа? Можна, і в багатьох випадках це дуже зручно, особливо якщо двійкове

число перевести в десяткову систему. Наприклад, якщо

А \u003d 0, В \u003d 1, С \u003d 1, D = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

т. е. заданий набір має номер 6 в десятковій системі.

Якщо за десятковим номером потрібно знайти значення аргументів, то

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

Нехай, наприклад, потрібно знайти значення аргументів А, В, С, D, Е, Fпо набору з номером 23. Переводимо число 23 в двійкову систему методом

поділу на два:

В результаті отримуємо 23 10 \u003d 10111 2. Це число п'ятизначне, а всього

аргументів шість, отже, зліва необхідно записати один нуль:

23 10 \u003d 010111 2. Звідси знаходимо:

А \u003d 0, В \u003d 1, С \u003d 0, D \u003d 1, Е \u003d 1, F \u003d 1.

Скільки всього існує наборів, якщо відомо число п аргументів? Очевидно, стільки ж, скільки існує n-розрядних двійкових чисел, т. Е. 2 \u200b\u200bn

лекція 6

Завдання булевої функції

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

На прикладі функції

з'ясуємо, як побудувати для неї таблицю відповідності.

Функція залежить від трьох аргументів А, В, С. Отже, в таблиці

передбачаємо три колонки для аргументів A, B, C і одну колонку для значень функції f. Зліва від колонки А корисно розмістити ще одну колонку. У ній будемо записувати десяткові числа, які відповідають наборам, якщо їх розглядати як Трехразрядное виконавчі номера. ця десяткова

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

нею можна знехтувати.

Заповнюємо таблицю. У рядку з номером ТОВ записано:

А \u003d В \u003d С \u003d0.

Визначимо значення функції на цьому наборі:

У колонці f записуємо нуль в рядку з набором 000.

Наступний набір: 001, т. е. А \u003d В \u003d 0, С \u003d 1. Знаходимо значення функції

на цьому наборі:

На наборі 001 функція дорівнює 1, отже, в колонці f в рядку з

номером 001 записуємо одиницю.

Аналогічно обчислюємо значення функцій на всіх інших наборах і

заповнюємо всю таблицю.

асоціативність

х 1 (х 2 х 3) \u003d (х 1 х 2) х 3;

х 1 Ú (х 2 Ú х 3) \u003d (х 1 Ú х 2) Ú х 3.

комутативність

х 1 х 2 \u003d х 2 х 1

х 1 Ú х 2 \u003d х 2 Ú х 1

Дистрибутивність кон'юнкції щодо диз'юнкції

х 1 (х 2 Ú х 3) \u003d х 1 х 2 Ú х 1 х 3.

Дистрибутивність диз'юнкції відносно кон'юнкції

х 1 Ú (х 2 × х 3) \u003d (х 1 Úх 2) × (х 1 Úх 3). *

Ідемпотентність (тавтологія)

подвійне заперечення

властивості констант

x & 1 \u003d x; (Закони універсальної множини)

x & 0 \u003d 0; (Закони нульового безлічі)

Правила (закони) де Моргана

Закон протиріччя (додатковості)

Закон виключення третього (додатковості)

Докази всіх цих формул тривіальні. Один з варіантів побудова таблиць істинності лівої і правої частин і їх порівняння.

Правила склеювання

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

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

правило поглинання

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

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

правило розгортання

Це правило визначає дію зворотне склеювання.

Правило розгортання елементарного твори в логічну суму елементарних творів більшого рангу (в межі до r \u003d n, тобто до констітуєнт одиниці, як і буде розглянуто нижче) випливає з законів універсальної множини, розподільного закону першого роду і проводиться в три етапи:

В розгортається елементарне твір рангу r вводиться в якості співмножників n-r одиниць, де n- ранг констітуенти одиниці;

Кожна одиниця замінюється логічної сумою деякої, чи не наявною в вихідному елементарному творі змінної і її заперечення: x i v `x i = 1;

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

Правило розгортання елементарного твори використовується для мінімізації функцій алгебри логіки (ФАЛ).

Правило розгортання елементарної суми рангу r до твору елементарних сум рангу n (констітуєнт нуля) слід їх законів нульового безлічі (6) і розподільного закону другого роду (14) і виробляється в три етапи:

В розгортається суму рангу r в якості доданків вводиться n-r нулів;

Кожен нуль представляється у вигляді логічного твори деякої, чи не наявною у вихідній сумі змінної і її заперечення: x i·` x i = 0;

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

16.Понятіе повної системи. Приклади повних систем (з доказом)

Визначення. Безліч функцій алгебри логіки A називається повною системою (в P2), якщо будь-яку функцію алгебри логіки можна виразити формулою над A.

Система функцій A \u003d ( f 1, f 1, ..., f m ), Що є повною, називається базисом.

Мінімальним базисом називається такий базис, для якого видалення хоча б однієї функції f 1 , Що утворює цей базис, перетворює систему функцій (F 1, f 1, ..., f m) в неповну.

Теорема. Система A \u003d (∨, &,) є повною.

Доведення. Якщо функція алгебри логіки f відмінна від тотожного нуля, то f виражається у вигляді досконалої диз'юнктивної нормальної форми, в яку входять лише диз'юнкція, кон'юнкція і заперечення. Якщо ж f ≡ 0, то f \u003d x & x. Теорема доведена.

Лемма. Якщо система A - повна, і будь-яка функція системи A може бути виражена формулою над деякою іншою системою B, то B - також повна система.

Доведення. Розглянемо довільну функцію алгебри логіки f (x 1, ..., x n) і дві системи функцій: A \u003d (g 1, g 2, ...) і B \u003d (h 1, h 2, ...). В силу того, що система A сповнена, функція f може бути виражена у вигляді формули над нею:

f (x 1, ..., x n) \u003d ℑ

де g i \u003d ℜ i

тобто функція f представляється у вигляді

f (x 1, ..., x n) \u003d ℑ [ℜ1, ℜ2, ...]

інакше кажучи, може бути представлена \u200b\u200bформулою над B. Перебираючи таким чином всі функції алгебри логіки, отримаємо, що система B також повна. Лема доведена.

Теорема. Наступні системи є повними в P 2:

4) (&, ⊕, 1) базис Жегалкина.

Доведення.

1) Відомо (теорема 3), що система A \u003d (&, V,) повна. Покажемо, що повна система B \u003d (V,. Дійсно, із закону де Моргана (x & y) \u003d (x ∨ y) отримуємо, що x & y \u003d (x ∨ y), тобто кон'юнкція виражається через диз'юнкцію і заперечення, і всі функції системи A виражаються формулами над системою B. Згідно лемі система B повна.

2) Аналогічно пункту 1: (x ∨ y) \u003d x & y ⇔ x ∨ y \u003d (x & y) і з леми 2 слід істинність затвердження пункту 2.

3) x | y \u003d (x & y), x | x \u003d x; x & y \u003d (x | y) \u003d (x | y) | (X | y) і відповідно до леми 2 система повна.

4) x \u003d x ⊕1 і відповідно до леми 2 система повна.

Теорема доведена.

17.Алгебра Жегалкина. Властивості операцій і повнота

Безліч булевих функцій, заданих в базисі Жегалкина S4 \u003d (⊕, &, 1) називається алгеброю Жегалкина.

Основні властивості.

1. коммутативность

h1⊕h2 \u003d h2⊕h1 h1 & h2 \u003d h2 & h1

2. асоціативність

h1⊕ (h2⊕h3) \u003d (h1⊕h2) ⊕h3 h1 & (h2 & h3) \u003d (h1 & h2) & h3

3. дистрибутивность

h1 & (h2⊕h3) \u003d (h1 & h2) ⊕ (h1 & h3)

4. властивості констант

5. h⊕h \u003d 0 h & h \u003d h
затвердження. Через операції алгебри Жегалкина можна висловити все інші булеві функції:

x → y \u003d 1⊕x⊕xy

x ↓ y \u003d 1⊕x⊕y⊕xy

18.Поліном Жегалкина. Способи побудови. Приклад.

Поліномом Жегалкина (поліномом по модулю 2) від n змінних x 1, x 2 ... x n називається вираз виду:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n,

де постійні C k можуть набувати значень 0 чи 1.

Якщо поліном Жегалкина не містить творів окремих змінних, то він називається лінійним (лінійна функція).

Наприклад, f \u003d x⊕yz⊕xyz і f 1 \u003d 1⊕x⊕y⊕z - поліноми, причому друга є лінійною функцією.

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

Наведемо основні методи побудови поліномів Жегалкина від заданої функції.

1. Метод невизначених коефіцієнтів. Нехай P (x 1, x 2 ... x n) - шуканий поліном Жегалкина, який реалізує задану функцію f (x 1, x 2 ... x n). Запишемо його у вигляді

P \u003d c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Знайдемо коефіцієнти C k. Для цього послідовно додамо змінним x 1, x 2 ... x n значення з кожного рядка таблиці істинності. В результаті отримаємо систему з 2 n рівнянь з 2 n невідомими, що має єдине рішення. Вирішивши її, знаходимо коефіцієнти полінома P (X 1, X 2 ... X n).

2. Метод, заснований на перетворенні формул над безліччю зв'язок (, &). Будують деяку формулу F над безліччю зв'язок (, &), що реалізує дану функцію f (X 1, X 2 ... X n). Потім замінюють всюди подформули виду A на A⊕1, розкривають дужки, користуючись дистрибутивним законом (див. Властивість 3), а потім застосовують властивості 4 і 5.

приклад. Побудувати поліном Жегалкина функції f (X, Y) \u003d X → Y

Рішення.
1. (метод невизначених коефіцієнтів). Запишемо шуканий поліном у вигляді:

P \u003d c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Користуючись таблицею істинності імплікації отримуємо, що

f (0,0) \u003d P (0,0) \u003d C 0 \u003d 1

f (0,1) \u003d P (0,1) \u003d C 0 ⊕C 2 \u003d 1

f (1,0) \u003d P (1,0) \u003d C 0 ⊕C 1 \u003d 0

f (1,1) \u003d P (1,1) \u003d C 0 ⊕C 1 ⊕C 2 ⊕C 12 \u003d 1

Звідки послідовно знаходимо, C 0 \u003d 1, C 1 \u003d 1, C 2 \u003d 0, C 12 \u003d 1

Отже: x → y \u003d 1⊕X⊕XY.

2. (Метод перетворення формул.). Маємо: x → y \u003d xvy \u003d (xy) \u003d (x (y⊕1)) ⊕1 \u003d 1⊕x⊕xy
Зауважимо, що перевага алгебри Жегалкина (в порівнянні з іншими алгебра) складається в арифметизации логіки, що дозволяє виконувати перетворення булевих функцій досить просто. Її недоліком в порівнянні з булевої алгеброю є громіздкість формул.

Схожа інформація.

Формули і закони логіки

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

НЕ запам'ятати, НЕ роздрукувати, а саме ще раз осмислити і власноруч переписати на папір - щоб вони були перед очима:

- таблиця НЕ;
- таблиця І;
- таблиця АБО;
- імплікаціонная таблиця;
- таблиця еквіваленціі.

Це дуже важливо. В принципі, їх було б зручно занумерувати «Таблиця 1», «Таблиця 2» і т.д., Але я неодноразово підкреслював вада такого підходу - як то кажуть, в одному джерелі таблиця виявиться першою, а в іншому - сто першої. Тому будемо використовувати «натуральні» назви. продовжуємо:

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

1) будь-які елементарні (прості) висловлювання;

2) якщо і - формули, то формулами також є вираження виду
.

Ніяких інших формул немає.

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

формулою нЕ є, наприклад, запис - і тут простежується очевидна аналогія з «алгебраїчним сміттям», з якого не зрозуміло - чи потрібно числа складати або множити.

Логічну формулу можна розглядати, як логічну функцію. Запишемо в функціональному вигляді ту ж кон'юнкцію:

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

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

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

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

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

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

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

Напевно, всі розуміють, але на всякий пожежний: і це дві різні формули! (Як у формальному, так і в змістовному плані)

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

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

На другому кроці дивимося на стовпці і і застосовуємо до них операцію АБО. Трохи забігаючи вперед, скажу, що диз'юнкція перестановки (І - це одне і те ж), І тому стовпці можна аналізувати в звичному порядку - зліва направо. При виконанні логічного складання зручно використовувати наступне прикладне міркування: «Якщо два нуля - ставимо нуль, якщо хоча б одна одиниця - одиницю»:

Таблиця істинності побудована. А тепер згадаємо стару-добру імплікації:

... уважно-уважно ... дивимося на підсумкові колонки .... В алгебрі висловлювань такі формули називаються рівносильними або тотожними:

(Три горизонтальні рисочки - це значок тотожності)

В 1-й частині уроку я обіцяв висловити імплікації через базові логічні операції, і виконання обіцянки не змусило себе чекати! Бажаючі можуть вкласти в імплікації змістовний сенс (Наприклад, «Якщо йде дощ, то на вулиці сиро») і самостійно проаналізувати рівносильне твердження.

сформулюємо загальне визначення: Дві формули називаються рівносильними (тотожними), Якщо вони приймають однакові значення при будь-якому наборі значень, що входять в ці формули змінних (Елементарних висловлювань). Також кажуть, що «Формули рівносильні, якщо збігаються їх таблиці істинності», Але мені не дуже подобається ця фраза.

Завдання 1

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

Ще раз повторимо порядок вирішення завдання:

1) Так як в формулу входять дві змінні, то все буде 4 можливих набору нулів та одиниць. Записуємо їх в обумовленому вище порядку.

2) імплікації «слабкіше» кон'юнкції, але вони розташовуються в дужках. Заповнюємо стовпець, при цьому зручно використовувати наступне прикладне міркування: «Якщо з одиниці слід нуль, то ставимо нуль, у всіх інших випадках - одиницю». Далі заповнюємо стовпець для імплікації, і при цьому, увага! - стовпці і слід аналізувати «справа наліво»!

3) І на завершальному етапі заповнюємо підсумковий стовпець. А тут зручно міркувати так: «Якщо в шпальтах і дві одиниці, то ставимо одиницю, у всіх інших випадках - нуль».

І, нарешті, звіряємося з таблицею істинності еквіваленціі .

Основні равносильности алгебри висловлювань

З двома з них ми тільки що познайомилися, але ними справа, звісно, \u200b\u200bне огранивать. Тотожностей досить багато і я перерахую найважливіші і найвідоміші з них:

Комутативність кон'юнкції і коммутативность диз'юнкції

комутативність - це перестановочность:

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

І, крім того, тут я знову хочу підкреслити формалізм математичної логіки. Так, наприклад, фрази «Студент здав іспит і випив» і «Студент випив і здав іспит» різні з змістовної точки зору, але невиразні з позицій формальної істинності. ... Таких студентів знає кожен з нас, і з етичних міркувань ми не буде озвучувати конкретних імен \u003d)

Асоціативність логічного множення і складання

Або, якщо «по-шкільному» - сполучна властивість:

дистрибутивні властивості

Зверніть увагу, що в 2-му випадку буде некоректно говорити про «розкриття дужок», в даному разі тут «фікція» - адже їх можна прибрати взагалі:, тому що множення - це сильніша операція.

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

закон ідемпотентності

Що робити, латинь ....

Прямо якийсь принцип здорової психіки: «я і я - це я», «я або я - це теж я» \u003d)

І тут же кілька схожих тотожностей:

... мда, щось я навіть подзавіс ... так і доктором філософії завтра можна прокинутися \u003d)

Закон подвійного заперечення

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

закони поглинання

- «а чи був хлопчик?» \u003d)

У правом тотожність дужки можна опустити.

Закони де Моргана

Припустимо, що строгий Викладач (Ім'я якого вам теж відомо :)) ставить іспит, якщо - Студент відповів на 1-е питання і – Студент відповів на 2-е питання. Тоді висловлювання, з якого випливає про те, що студент нЕ Здав екзамен, Буде рівносильно твердженням - студент нЕ відповів на 1-е питання або на 2-й питання.

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

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

В результаті «на виході» отримана формула, істинність якої збігається з істинністю висловлювання. Равносильность доведена.

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

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

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

Далі складемо таблицю істинності для правої частини. Тут теж все прозоро - в першу чергу проводимо більш «сильні» заперечення, потім застосовуємо до стовпців правило І:

Результати збіглися, таким чином, тотожність доведено.

Будь-яку равносильность можна представити у вигляді тотожно істинною формули . Це означає що ЗА БУДЬ-вихідному наборі нулів і одиниць «На виході» виходить строго одиниця. І цьому є дуже просте пояснення: так як таблиці істинності і збігаються, то, зрозуміло, вони еквівалентни.Соедінім, наприклад, еквіваленціі ліву і праву частину щойно доведеного тотожності де Моргана:

Або, якщо компактніше:

завдання 2

Довести наступні равносильности:

б)

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

Ми продовжуємо розгляд до законів логіки!

Так, абсолютно вірно - ми з ними вже щосили працюємо:

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

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

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

Фірмовий приклад суперечності від древніх греків:
- ніяке висловлювання не може бути істинним і хибним одночасно.

Доказ тривіально:

«На виході» отримані виключно нулі, отже, формула дійсно тотожна помилкова.

Однак і будь-яка суперечність - це теж закон логіки, зокрема:

Не можна осягнути таку розлогу тему в одній-єдиній статті, і тому я обмежуся ще лише кількома законами:

Закон виключеного третього

- в класичній логіці будь-яке висловлювання істинно або хибно і третього не дано. «Бути чи не бути» - ось в чому питання.

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

контрапозиція

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

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

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

І знову повернемося до наших змістовним прикладів: для висловлювань - число ділиться на 4, - число ділиться на 2 справедливі пряма і протилежна теореми, але помилкові зворотна і протилежна зворотного теореми. Для «дорослої» ж формулювання теореми Піфагора істинні всі 4 «напряму».

закон силогізму

Теж класика жанру: «Все дуби - дерева, всі дерева - рослини, отже, все дуби - рослини».

Ну і тут знову хочеться відзначити формалізм математичної логіки: якщо наш суворий Викладач думає, що якийсь Студент - є дуб, то з формальної точки зору даний Студент, безумовно, рослина \u003d) ... хоча, якщо задуматися, то може бути і з неформальної теж \u003d )

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

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

2) до стовпців застосовуємо правило І;

3) ось тепер виконуємо;

4) і на останньому етапі застосовуємо імплікації до стовпців і.

Не соромтеся контролювати процес вказівним і середнім пальцем :))


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

завдання 3

З'ясувати, чи буде бути законом логіки наступна формула:

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

Перетворення логічних формул

Крім свого «логічного» призначення, равносильности широко використовуються для перетворення і спрощення формул. Грубо кажучи, одну частину тотожності можна міняти на іншу. Так, наприклад, якщо в логічній формулі вам зустрівся фрагмент, то згідно із законом ідемпотентності замість нього можна (і потрібно) записати просто. Якщо ви бачите, то згідно із законом поглинання спрощуйте запис до. І так далі.

Крім того, є ще одна важлива річ: тотожності справедливі не тільки для елементарних висловлювань, а й для довільних формул. Так наприклад:

, Де - будь-які (Як завгодно складні) формули.

Перетворимо, наприклад, складну імплікації (1-е тотожність):

Далі застосуємо до дужки «складний» закон де Моргана, при цьому, в силу пріоритету операцій, саме закон, де :

Дужки можна прибрати, тому що всередині знаходиться більш «сильна» кон'юнкція:

Ну, а з коммутативностью взагалі все просто - навіть позначати нічого не потрібно ... щось запав мені в душу закон силогізму :))

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

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

В якості тренування упросив формулу.

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

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

(1) Використовуємо тотожність . А нашому випадку.

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

(2) До зовнішніх дужках застосовуємо закон де Моргана, де.

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

Для довільних множин А, В, і С справедливі наступні тотожності (табл. 3.1):

Таблиця 3.1

1. Закон тотожності
2. Комутативність об'єднання	2 '. комутативність перетину
3. Асоціативність об'єднання	3 '. асоціативність перетину
4. Дистрибутивність об'єднання щодо перетину	4 '. Дистрибутивність перетину щодо об'єднання
5. Закони дії з порожнім і універсальнимU множинами (Закон виключення третього)	5 '. Закони дії з порожнім і універсальнимU множинами (Закон протиріччя)
6. Закон ідемпотентності об'єднання	6 '. Закон ідемпотентності перетину
7. Закон де Моргана	7 '. Закон де Моргана
8. Закон елімінації (поглинання)	8 '. Закон елімінації (поглинання)
9. Закон склеювання	9 '. закон склеювання
10. Закон Порецкого	10 '. закон Порецкого
11. Закон інволюції (подвійного доповнення)

Закони алгебри множин по відношенню до операцій перетину () і об'єднання () підпорядковані принципу подвійності: якщо в будь-якому законі все знаки перетину замінити знаками об'єднання, а все знаки об'єднання - знаками перетину, знак універсуму (U) замінити знаком порожнього безлічі (Ø), а знак порожнього - знаком універсуму, то отримаємо знову вірне тотожність. Наприклад (в силу цього принципу), з слід і т. П.

3.1. Перевірка істинності тотожностей за допомогою діаграм Ейлера-Венна

Всі закони алгебри множин можна наочно уявити і довести, використовуючи діаграми Ейлера-Венна. Для цього необхідно:

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

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

Дане тотожність істинно тоді і тільки тоді, коли на обох діаграмах заштрихована одна і та ж область.

Зауваження 3.1.Два пересічних кола ділять все універсальне безліч на чотири області (див. Рис.3.1)

Зауваження 3.2. Три пересічних кола ділять все універсальне безліч на вісім областей (див. Рис.3.2):

Зауваження 3.2. При записи умов різних прикладів часто використовуються позначення:

 - з ... слід ...;

 - тоді і тільки тоді, коли ....

завдання 3.1 . Спростити вирази алгебри множин:

Рішення.

завдання 3 .2 . Довести тотожності:

(АВ) \\ В \u003d А \\ В;

А (ВС) \u003d А \\ (А \\ В)  (А \\ С).

Рішення.

завдання 3.3 . Довести наступні співвідношення двома способами: за допомогою діаграм і за допомогою визначення рівності множин.

Рішення.

2. Доказ за допомогою визначення рівності множин.

За визначенням, безлічі Х і Y рівні, якщо одночасно виконані співвідношення: XY і YX.

Спочатку покажемо, що
. нехай х - довільний елемент множини
, тобто х
. Це означає, що хU і х
. Звідси випливає, що хА або хВ. якщо хА, то тоді хĀ, а значить,
. Якщо ж хВ, то
, а значить,
. Таким чином, будь-який елемент множини.
. є також елементом множини
Тобто

Тепер доведемо зворотне, тобто, що
. нехай
. якщо хĀ, то хU і хА, а значить, хАВ. Звідси слідує що
. Якщо ж
, то хU і хВ. значить, хАВ, тобто
. Звідси випливає, що будь-який елемент безлічі
є також елементом множини
, тобто
.

значить,
, що і потрібно було довести.

A (BC) \u003d (AB)  (AC);

1. Доказ за допомогою діаграми:

нехай хА (ВС). тоді хА і хВС. якщо хВ, то хАВ, що ні суперечить сказаному, а значить, х (АВ)  (АС). Якщо ж хС, то хАС. отже, х (AB)  (AC). Отже, доведено, що A (BC)  (AB)  (AC.

нехай тепер х (AB)  (AC). якщо хАВ, то хА і хВ. Звідси слідує що хА і хВС, тобто хА (ВС). Якщо ж хАС, то хА і хС. Звідси випливає, що хА і хВС, тобто хА (ВС). Таким чином, (AB)  (AC)  A (BC). Отже, A (BC) \u003d (AB)  (AC). Що і потрібно було довести.

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

2. Доказ за допомогою визначення рівності множин.

Необхідність. Нехай АВС і елемент хА. Покажемо, що в цьому випадку елемент множини А буде також і елементом безлічі
.

Розглянемо два випадки: хВ або
.

якщо хВ, то хАВС, тобто хС, і, як наслідок цього,
.

Якщо ж
, То і
. Необхідність доведена.

нехай тепер
і хАВ. Покажемо, що елемент хтакож буде елементом безлічі С.

якщо хАВ, тоді хА і хВ. оскільки
, значить хС. Достатність доведена.

1. Доказ за допомогою діаграми:

2. Доказ за допомогою визначення рівності множин.

Нехай АВ. Розглянемо елемент хВ (або
). аналогічно: хА (або хĀ). Тобто будь-який елемент безлічі є також елементом множини Ā. А це може бути у випадку, якщо
. Що і потрібно було довести.

Завдання 3.4. Висловити символічно зазначені області і спростити отримані вирази.

Рішення.

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

М \u003d ( x xA і хВ і хС або хС і хА і хВ).

З визначення операцій над множинами отримаємо:

М \u003d ((АВ) \\ С)  (С \\ А \\ В).

Запишемо цей вираз за допомогою основних операцій - доповнення, об'єднання і перетину:

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

Дану область можна розглядати як об'єднання множин А \\ В \\ С і АВС. За визначенням M \u003d ( x xA і xВ і хС або хА і хВ і хС). спростимо:

Завдання для самостійного рішення.

1. спростити:

2. Довести за допомогою діаграм, законів алгебри множин і визначення рівності множин:

(АВ) \\ В \u003d А \\ В;

А (ВС) \u003d А \\ (А \\ В)  (А \\ С);

АВ \u003d АВ  А \u003d В;

А \\ В \u003d   АВ \u003d А.

3. З'ясувати, чи існує безліч Х, яке задовольняє при будь-якому А рівності:

АХ \u003d А; (Відповідь );