Логика. логіка. Математична логіка та теорія алгоритмів

• Название: Математична логіка та теорія алгоритмів
• Анкор: Логика
• Дата: 15.05.2022
• Размер: 1.6 Mb.
• Имя файла: логіка.pdf
• Тип: Навчальний посібник; #530647
• страница: 5 из 18

1.5 ТЕХНІЧНІ ЗАСТОСУВАННЯ АЛГЕБРИ БУЛЕВИХ ФУНКЦІЙ
Комбінаційна схема (КС) – технічний пристрій, який служить для перетворення дискретних повідомлень і має n входів і m виходів і такий, що сукупність вихідних сигналів в кожний дискретний момент часу однозначно визначається вхідними сигналами, які подаються на вхід в той самий момент часу. Сигнали, які подаються на входи і знімаються з виходів, можуть приймати тільки значення “1” і “0”. Такими сигналами можуть, наприклад, бути високий і низький рівні напруги. Отже КС перетворює деяке n-буквене слово в двійковому алфавіті в m-буквенне слово в тому самому алфавіті.
КС найчастіше будують з елементарних логічних елементів, які реалізують найпростіші логічні операції.
Умовні позначення базових логічних елементів показано нижче.
Маючи запас таких елементів, можна будувати більш складні схеми, під’єднуючи виходи одних елементів до входів інших. Якщо при таких
НЕ (¬)
АБО-НЕ
(↓)
І-НЕ (|)
АБО (V)
І (Λ)


32
з’єднаннях уникати виникнення замкнутих контурів (наприклад, під’єднання виходу елемента на один з його власних входів), то отримуємо комбінаційну схему. Такі схеми знаходяться в однозначній відповідності з формулами булевої алгебри, так, що з їх допомогою може бути виражена будь-яка система булевих функцій.
Логічний елемент, який реалізує операцію заперечення, називається елементом «НЕ», або інвентором. Він має один вхід, на який подається сигнал, що відповідає булевій змінній х (якщо є сигнал, то х=1, якщо немає сигналу -
х=0), і один вихід, на якому виникає сигнал
x
. Логічний елемент, який реалізує операцію кон’юнкції, називається елементом «І», або збігом. Логічний елемент, який реалізує операцію диз’юнкції, називається елементом
«АБО»
(відокремленням). Логічний елемент «» реалізує операцію заперечення еквіваленції (її ще називають сумою Жегалкіна, виключним додаванням, додаванням за модулем 2). Елементи «І-НЕ» і «АБО-НЕ» відповідно реалізують операції штрих Шеффера і стрілку Пірса.
Очевидно, що кількість базових елементів можна було б зменшити, залишивши лише ті, які відповідають якій-небудь одній функціонально повній системі логічних операцій. Теоретично основними базовими логічними операціями як правило називають заперечення, кон’юнкцію та диз’юнкцію і відповідно елементи «НЕ», «І», «АБО» - основними базовими логічними елементами . Проте на практиці з технологічних причин зручно буває мати дещо
інший їх набір.
КС можна утворити, з’єднуючи виходи одних логічних елементів з входами
інших. Схема, яка має n входів і один вихід, реалізує деяку n-місну логічну
(булеву) функцію. Так, булевій функції, яка зображується формулою
z
y
x
z
y
x
f



)
,
,
(
відповідатиме комбінаційна схема:
Часто доводиться розв’язувати задачі на аналіз та синтез схем.
Задача синтезу КС полягає в тому, щоб для заданої булевої функції побудувати комбінаційну схему, що її реалізує.
Задача аналізу комбінаційної схеми полягає в тому, щоб математично описати цю схему (побудувати її математичну модель), тобто знайти відповідну

33
логічну формулу булевої функції. Таку задачу можна розв’язати, розкладаючи схему на підсхеми. Знайдену логічну формулу доцільно, по можливості спростити, замінивши такою рівносильною формулою, яка містить меншу кількість елементів.
Приклад 1. Реалізувати комбінаційною схемою наступну булеву функцію
).
(
)
(
)
(
)
,
,
(
x
y
z
y
y
x
z
y
x
f






Дана булева функція містить три змінні, які подаються на вхід нашої схеми, а також лише операції, що відповідають базовим логічним елементам комбінаційних схем: стрілка Пірса, заперечення, диз’юнкція. Порядок виконання операцій в булевій функції повинен відповідати послідовності з’єднань змінних логічними елементами та самих логічних елементів. Тому шукана комбінаційна схема має вид:
Приклад 2. Спростити комбінаційну схему:
Запишемо формулу булевої функції, яка відповідає даній схемі:
)
(
)
(
)
,
,
(
b
c
a
b
a
c
b
a
f





Нам потрібно отриману формулу максимально спростити:















)
(
)
(
)
(
)
(
)
(
)
(
b
c
a
b
a
b
c
a
b
a
b
c
a
b
a















)
(
)
(
)
(
)
(
)
(
)
(
b
c
a
a
b
b
a
b
c
a
a
b
b
a
a
b
b
c
a
b
b
c
a
a
a
b
b
c
a
a
b

















)
(
)
(
)]
(
)
[(
)
(
)
(
Для отриманої формули побудуємо комбінаційну схему:

34
Одним із способів фізичної реалізації комбінаційних схем є релейно- контактні схеми, які дають можливість реалізувати логічні операції шляхом замикання і розмикання контактів окремих електричних кіл.
Під релейно-контактною (РКС) схемою розуміють пристрій із провідників і двопозиційних контактів. Двопозиційний контакт – це фізичне тіло, яке може перебувати лише в двох станах – “ввімкнуто” і “вимкнуто”, які будемо позначати
1 і 0 відповідно. Контакти позначатимемо малими латинськими літерами.
Між собою контакти можуть з’єднуватись послідовно і паралельно:
Послідовне з’єднання провідників реалізує операцію кон’юнкції (сигнал через з’єднання контактів проходить тоді і тільки тоді, коли він проходить через кожний контакт).
Паралельне з’єднання провідників реалізує операцію диз’юнкції (сигнал через з’єднання контактів не проходить тоді і тільки тоді, коли він не проходить через жодний контакт з’єднання).
Послідовне з’єднання контактів позначатимемо xy, а їх паралельне з’єднання
x+y. Через
x
будемо позначати контакт, який проводить сигнал тоді і тільки тоді, коли сигнал х його не проводить.
Отже, кожній РКС відповідає деяка формула алгебри висловлень, утворена за допомогою функціонально повної системи логічних операцій {



,
,
} і, навпаки, кожній такій формулі відповідає деяка контактна схема.
Аналогічно тому, як і в логіці висловлень не цікавляться змістом висловлень, а тільки тим, істинні вони чи хибні, так і при розгляді структурної формули цікавляться тільки «значенням замкнутості» схеми (чи схема проводить сигнал).
Тому функцію, яка реалізується схемою, називають функцією провідності схеми.
Очевидно, що схема буде замкнена тоді і тільки тоді, коли значення її функції провідності дорівнює 1. Тому дві контактні схеми називають рівносильними, якщо при одних і тих самих значеннях вхідних і вихідних контактів кожна з них

35
проводить сигнал тоді і тільки тоді, коли його проводить інша. Інакше, дві схеми рівносильні тоді і тільки тоді, коли їх структурні формули рівносильні.
Задачею аналізу РК схеми називають задачу знаходження булевої функції
(функції провідності), яку реалізує ця схема.Задача спрощення РК схем називається задачею мінімізації, а задача побудови релейно-контактних схем, що реалізують задані булеві функції є задачею синтезу РК схем.
Приклад 3. Максимально спростити РК- схему:
За схемою запишемо відповідну їй формулу контактних схем, спростимо формулу шляхом рівносильних перетворень і за спрощеною формулою побудуємо спрощену контактну схему:















)
)(
)(
)(
(
)
)(
)(
)(
(
c
a
d
c
d
c
c
a
b
c
b
a
d
c
b
d
c
b
c
b
a
d
c
b
d
c
c
c
a
a
b






)]
)(
[(
Отже, отримали спрощену схему, рівносильну заданій:
Запитання для самоконтролю
1. Що називають комбінаційною схемою (КС)?
2. З яких елементарних логічних елементів будують КС?
3.
Яку булеву функцію реалізує кожен елементарний логічний елемент?
4. В чому суть задач синтезу та аналізу комбінаційної схеми?
5. Що називають релейно-контактною схемою (РКС)?
6. Які способи з’єднання контактів в РКС? Якими логічними операціями вони реалізуються?
7. Що називається функцією провідності РКС?
8. Які релейно-контактні схеми називають рівносильними?
9. В чому суть задач синтезу та аналізу РКС?
10. В чому суть задачі мінімізації релейно-контактної схеми?
ВПРАВИ
1.35Побудувати комбінаційні схеми, що реалізують наступні булеві функції:

36
a)
)
)
(
(
z
z
x
x
y




; b)




z
y
y
x


/
; c)


)
/
)
/(
(
x
z
x
y
y
z



; d)


))
(
(
z
x
y
y
z




; e)
)
)
(
(
))
(
(
z
z
x
x
y
z
z
x







;
1.36 Побудувати РК-схеми, функції провідності яких визначаються наступними формулами: a)
; b)
; c)
; d)
; e)
;
1.37 Максимально спростити РК-схеми: а) б) в) г)
1.38 Максимально спростити комбінаційні схеми. а) б)

37
в) г)
1.39 З n (n=2,3,4,…) контактiв скласти релейно-контактну схему, яка б спрацьовувала тоді й лише тоді, коли ввімкнено деякі, але не всі контакти.
1.40 Мiж поверхами двоповерхового будинку є одна лампа. Побудувати РК схему так, щоб на кожному поверсі можна було вимикачем включати i виключати світло незалежно вiд положення іншого вимикача.
1.41 Потрібно, щоб у великій залi можна було включати i виключати світло за допомогою будь-якого з чотирьох вимикачів, що розташовані на чотирьох стiнах залу. Скласти відповідну РК схему.
1.42 Комітет складається з п’яти осіб, рішення приймається бiльшiстю голосів.
Якщо голова голосує проти, рішення не приймається. Скласти таку схему, щоб голосування відбувалось натисканням на кнопку, i у випадку, коли рішення прийняте, включалась лампа.
1.43 З n контактів скласти релейно-контактну схему, яка б спрацьовувала тодi й тiльки тодi, коли замкнено не бiльше k контактiв.
1.6 ВІДНОШЕННЯ ЛОГІЧНОГО НАСЛІДКУ
Довести математичну теорему – це значить, виходячи з її умови, за певними правилами одержати висновок. У цьому випадку кажуть, що висновок теореми є
«логічним наслідком» з умови або, що він виводиться з умови. Аналогічно проводяться будь-які доведення: будується ланцюжок тверджень, кожне з яких є або вихідним, або слідує з раніше встановлених, причому термін «слідує» не з’ясовується, а вважається відомим і цілком зрозумілим з логіки. Математична логіка дає точне визначення поняття слідування (вивідності).
Коли говорять, що з одного чи декількох тверджень
m
A
A
A
,...
,
2 1
слідує твердження В, то розуміють наступне: кожного разу, коли твердження
,
m
A
A
A
,...
,
2 1
є істинними, істинним буде і твердження В.

38
Завдання алгебри висловлень полягає в тому, щоб вказати такі форми висловлень
m
A
A
A
,...
,
2 1
,В, при яких висловлення В обов’язково слідує з попередніх висловлень незалежно від конкретного змісту всіх цих висловлень. Але форми висловлень виражаються формулами алгебри висловлень. Тому теорія логічного слідування на базі алгебри висловлень вивчає закономірності утворення таких формул
m
A
A
A
,...
,
2 1
, В, що перші m формул зв’язані з останньою відношенням логічного слідування.
Означення. Формула В логічно слідує (є логічним наслідком) з формул
m
A
A
A
,...
,
2 1
, якщо вона набуває значення істинності «1» для кожного такого набору значень пропозиційних змінних, при якому всі формули
m
A
A
A
,...
,
2 1
мають значення істинності «1».
Позначення:
B
A
A
A
m

,...
,
2 1
При цьому формули
m
A
A
A
,...
,
2 1
називають посилками, гіпотезами або припущеннями, а формулу В – логічним висновком, логічним наслідком.
Для порожньої множини посилок маємо
B

, що цілком узгоджується зі скороченням твердження «В є тавтологією».
Приклад 1. За таблицею істинності визначити, які з наступних формул:
b
a 
,


c
b
a


,


c
b
a


, є логічними наслідками інших.
Побудуємо таблиці істинності даних формул:
|а|
|в|
|с|
|
b
a 
|
|


c
b
a


|
|


c
b
a


|
0 0
0 1
1 1
0 0
1 1
1 1
0 1
0 1
1 1
0 1
1 1
1 1
1 0
0 0
1 1
1 0
1 0
1 0
1 1
0 1
0 0
1 1
1 1
1 1
При з’ясуванні, чи є одна формула логічним наслідком множини формул, якщо побудовано їх таблиці істинності, треба визначити всі набори змінних, де досліджувана формула набуває значення 0. Якщо хоч на одному з цих наборів всі формули з множини формул набувають значення 1, то логічний наслідок не має місця.
Розглянемо формулу
b
a 
. З таблиці видно, що в 5-му рядку вона набуває значення 0, тому не є логічним наслідком формул


c
b
a


та

39


c
b
a


. Друга формула


c
b
a


не є логічним наслідком формули
b
a 
, оскільки набуває значення 0 на 7-му наборі, де значення /
b
a 
/=1, але є логічним наслідком формули


c
b
a


. Очевидно, також, що третя формула


c
b
a


є логічним наслідком з першої та другої формули:
b
a 
,


c
b
a





c
b
a


На практиці відношення логічного наслідку часто застосовується не до формул, а до висловлень, сформульованих природною мовою.
Означення. Нехай
m



,...,
,
2 1
-міркування і  - висновок цих міркувань, а
B
A
A
A
m
,
,...
,
2 1
- формули алгебри висловлень, що відповідають їх логічним структурам. Кажуть, що міркування
m



,...,
,
2 1
логічні і висловлення  є правильним (логічним) висновком, тоді і тільки тоді, коли формула В логічно слідує з формул
m
A
A
A
,...
,
2 1
Приклад 2. Дослідити міркування на логічність методом від супротивного:
«Якщо капіталовкладення залишаться постійними, то виростуть урядові витрати або виникне безробіття. Якщо урядові витрати не виростуть, то податки будуть знижені. Якщо податки будуть знижені і капіталовкладення залишаться постійними, то безробіття не виникне. Отже, урядові витрати виростуть.»
Розв’язання. Побудуємо логічну структуру цього міркування. Для цього спочатку виділимо прості висловлення:
«Капіталовкладення залишаться постійними» - a;
«Виростуть урядові витрати» - b;
«Виникне безробіття» - с;
«Податки будуть знижені» - d.
Логічною структурою міркування буде наступна послідовність формул:
b
B
c
a
d
A
d
b
A
c
b
a
A









,
,
,
3 2
1
Міркування буде логічним, за означенням, тоді і тільки тоді, коли формула В логічно слідує з формул
3 2
1
,
,
A
A
A
. Тобто .
b
c
a
d
d
b
c
b
a






,
,
Припустимо, від супротивного, що логічний наслідок стоїть невірно, тобто
існує набір змінних (
d
c
b
a
,
,
,
) для яких виконується система умов:

40
 



























































0 1
,
0 1
0 0
1 1
1 0
1 1
1 1
0 0
1 1
1
b
c
d
a
b
c
a
d
c
a
b
c
a
d
d
c
a
b
c
a
d
d
b
c
b
a
Таким чином знайдено такі набори змінних ((0,0,0,1), (0,0,1,1)), при яких кожне з припущень буде істинним, а висновок – хибним. Отже, висновок, що урядові витрати виростуть не є правильним, а міркування не логічні.