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

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

Запитання для самоконтролю
1. Що називать висловленням?
2. Які припущення лежать в основі класичної двозначної логіки?
3. Що називають пропозиційними буквами (змінними)?
4. Як називаються основні логічні операції алгебри висловлень? Дайте означення кожної з них.
5. Що називають літералом в алгебрі висловлень?
6. Які символи утворюють алфавіт алгебри висловлень?
7. Що називають формулою алгебри висловлень?
8. Які правила щодо скорочення дужок застосовуються у формулах алгебри висловлень?
9. Як будується таблиця істинності формули
)
,...
,
(
2 1
n
a
a
a
A
? Скільки рядків вона містить?

11 10. Яка формула називається а) тавтологією, б) суперечністю, в) виконуваною, г) спростовною, д) нейтральною? Наведіть приклади формул кожного типу.
11. Якщо формула
)
,...
,
(
2 1
n
a
a
a
A
тавтологія, якою буде формула
)
,...
,
(
2 1
n
a
a
a
A
?
12. Якщо формула
)
,...
,
(
2 1
n
a
a
a
A
нейтральна, якою буде формула
)
,...
,
(
2 1
n
a
a
a
A
?
13. Якщо формула
)
,...
,
(
2 1
n
a
a
a
A
суперечність, якою буде формула
)
,...
,
(
2 1
n
a
a
a
A
?
14. Скільки різних наборів пропозиційних змінних існує для формули
)
,...
,
(
2 1
n
a
a
a
A
?
15. Якщо формули
B
A
А

,
тавтології, то що можна сказати про формулу
В?
ВПРАВИ.
1.1 Які з наступних речень є висловленнями? a) до університету вступають найкращі учні; b) для будь-якого дійсного числа x: |sin x| ≤ 1; c) математична логіка; d) подивіться в підручник; e)
3 – парне число; f)
Київ – столиця України; g) взимку завжди йде сніг.
1.2 Записати висловлення: «Числа 10 і 8 є парними числами» за допомогою таких простих висловлень: “число 10 – парне” – a, “число 8 – непарне” –b.
1.3 Прочитайте наступні формули природною мовою: а)
d
c 
, б)
b
c
a


, в)
a
b 
, г)
d
c
a


, д)
a
d
c
b



, якщо a: «цей чотирикутник – паралелограм»,
b: «цей чотирикутник – ромб», c: «цей чотирикутник – прямокутник», d: «цей чотирикутник – квадрат».
1.4 Записати висловлення у вигляді формули, позначивши літерами атомарні висловлення, тобто не побудовані з інших висловлень: a) якщо собака гавкає, то господар не спить, і якщо господар не спить, то собака гавкає; b) або Петро піде на заняття, і Дмитро туди не піде, або Петро не піде на заняття, і Дмитро відмінно проведе час; c) необхідна й достатня умова для щастя студента полягає в тому, щоб пити пиво, багато спати і насолоджуватися музикою;

12
d)
Іван дивиться телевізор тільки в тому випадку, коли там показують бойовик; e) корінь із цілого числа є або цілим, або ірраціональним числом; f) для того, щоб X було непарним, достатньо, щоб X було простим; g) необхідною умовою того, що послідовність збігається, є її обмеженість.
1.5 Записати висловлення у вигляді формули і побудувати таблицю істинності: a) якщо число ділиться на 5 і не ділиться на 2, то воно не ділиться на 10; b)
Петро вступить до університету тоді і тільки тоді, коли буде добре вчитися і отримає високий бал на вступних іспитах; c) якщо після дощу ясно, то на небі з’явиться веселка і буде тепло; d) якщо дитина плаче, то вона або хоче їсти, або в неї щось болить; e) студент виконує завдання довго тоді і тільки тоді, коли вони складні або він погано знає матеріал; f) якщо число просте, то воно ділиться або на 1, або саме на себе; g) якщо протягом семестру я буду гарно вчитися і матиму хороші оцінки, то здам успішно сесію і буду отримувати стипендію.
1.6За допомогою таблиці істинності визначити тип формули:
a)
a
b
a


; b)
b
b
a


; c)



 

c
b
a
b
c
a
b






; d)
b
c
a
b
a




; e)






c
b
a
c
b
a





; f)




c
b
c
b
b
a





; g)








c
b
b
c
a
a
b
a







; h)



 
 

d
a
c
b
d
c
b
a







1.7 Довести, що якщо формули
B
A 
і
C
A 
є тавтологіями, то
C
B 
також тавтологія.
1.8 За допомогою методу від супротивного переконатися, чи будуть тавтологіями наступні формули: a)
; b)
; c)
)
(
)
)
((
)
)
((
r
q
p
r
q
p
r
q
p








; d)
))
(
)
((
))
(
)
((
s
q
r
p
s
r
q
p







1.9 Розглядається справа Брауна, Джонса і Сміта. Один з них здійснив злочин. На слідстві кожен з них зробив дві заяви.

13
Браун: «Я не винен. Сміт зробив це.»
Джонс: «Сміт не винен. Браун зробив це.»
Сміт: «Я не робив цього. Джонс не робив цього.»
Суд встановив, що один з них двічі сказав неправду, другий двічі сказав правду, третій – один раз правду, другий раз збрехав. Хто здійснив злочин?
1.10 Чотири спортсмени – Андрій, Іван, Роман і Сергій в змаганнях посіли перші чотири місця, причому жодне з місць не було поділене між ними. Про зайняті місця є інформація: «Друге місце посів Роман, а третє Сергій», «Переміг Роман,
Іван був другим», «Друге місце посів Андрій, а Сергій останнє». Як розподілились місця між учасниками змагань, якщо відомо, що в кожному з трьох висловлень про зайняті місця одне твердження істинне, а друге хибне?
1.11 При яких натуральних n (n - кількість входжень змінної x) формула: a)
x
x
x
x




...)
)
)
(...(
є тавтологією; b)
x
x
x
x




...)
)
)
(...(
є нейтральною; c)
x
x
x
x




...)
)
)
(...(
є виконуваною; d)
...)
)
)
)
(...(




x
x
x
x
є суперечністю.
1.12На змаганнях легкоатлетів із спортивної ходьби Андрій відстав від Богдана та ще від двох спортсменів. Віктор фінішував після Дмитра, але раніше Геннадія.
Дмитро випередив Богдана, але прийшов після Євгена. Яке місце займає кожний спортсмен?

14
1.2 ВІДНОШЕННЯ РІВНОСИЛЬНОСТІ НА БАЗІ АЛГЕБРИ
ВИСЛОВЛЕНЬ
Формули
)
,...
,
(
2 1
n
a
a
a
A
і
)
,...
,
(
2 1
n
a
a
a
B
алгебри висловлень називаються
рівносильними (логічно еквівалентними), якщо вони мають однакові значення
істинності на кожному з усіх наборів логічних значень пропозиційних змінних, тобто набувають однакових значень в усіх інтерпретаціях.
Позначення:
B
A 
. Символ « » не є символом операції алгебри висловлень, а означає певне відношення між формулами; він належить не предметній мові алгебри висловлень, а метамові. Означення рівносильних формул можна записати символічно:




)
,...,
,
(
)
,...,
,
(
2 1
2 1
n
n
a
a
a
B
a
a
a
A
B
A



Теорема 1.2.1 (ознака рівносильності формул). Дві формули А і В алгебри висловлень рівносильні тоді і тільки тоді, коли формула А↔В є тавтологією:




B
A
B
A




Наслідок. Відношення рівносильності між формулами алгебри висловлень має властивості: а) рефлексивність:
A
A 
; б) симетричність: якщо
B
A 
, то
A
B 
; в) транзитивність: якщо
B
A 
і
C
B 
, то
C
A 
тобто відношення рівносильності є відношенням еквівалентності.
Теорема 1.2.2 (основні рівносильності алгебри висловлень). Справедливими
є наступні рівносильності:
1.
a
b
b
a



,
a
b
b
a



(комутативні закони);
2.
c
b
a
c
b
a





)
(
)
(
,
c
b
a
c
b
a





)
(
)
(
(асоціативні закони);
3.
)
(
)
(
)
(
c
a
b
a
c
b
a






,
)
(
)
(
)
(
c
a
b
a
c
b
a






(дистрибутивні
закони);
4.
a
a
b
a



)
(
,
a
a
b
a



)
(
(закони поглинання);
5.
b
a
b
a



,
b
a
b
a



(закони де Моргана);
6.
b
a
b
a



;
7.

 

a
b
b
a
b
a





;
8.
a
a 
(закон подвійного заперечення);
9.
a
a
a


,
a
a
a


(закони ідемпотентності);
10.
a
a

 1
,
1 1 

a
;
11.
0 0 

a
,
a
a

 0
;

15 12.
0

 a
a
(закон протиріччя);
13.
1

 a
a
(закон виключеного третього);
14.
1

 a
a
(закон виключення суперечності).
Використовуючи рівносильності з теореми 1.2.2, можемо від однієї формули перейти до рівносильної їй формули. Такий перехід називається рівносильним
перетворенням вихідної формули.
Для рівносильних перетворень та спрощень формул поряд з основними рівносильностями важливе значення має правило заміни.
Теорема 1.2.3 (про заміну).
Нехай
B
A 
і С – деяка підформула формули А, причому
*
C
C 
. Тоді формула
*
A
, одержана з формули А заміною підформули С на С
*
, рівносильна формулі В.
Відмітимо, що коли деяка формула є тавтологією, то і всяка рівносильна їй формула також є тавтологією:
)
(
)
,
(
B
B
A
A




Це дозволяє виявити ще одну сферу застосування рівносильних перетворень, зокрема, для доведення тотожної істинності (чи тотожної хибності) тих або інших формул. Для цього дану формулу потрібно рівносильними перетвореннями звести до формули, яка очевидно є тавтологією (суперечністю).
Приклад 1. Довести рівносильність




b
a
b
a
b
a





Розв’язання: Будемо виконувати рівносильні перетворення відносно лівої частини формули:

 b
a

 

a
b
b
a



Далі застосувавши закон
b
a
b
a



до обох імплікацій одержимо

 

a
b
b
a



. Скориставшись дистрибутивними законами дістанемо










)
(
)
(
a
b
a
b
b
a

 
 



a
b
a
a
b
b
b
a








. Застосувавши закони
, а отримаємо потрібний результат




b
a
b
a



Оскільки відношення рівносильності транзитивне, то процес доведення можна записати у вигляді дедуктивного ланцюга рівносильних перетворень:

 b
a

 





a
b
b
a

 





a
b
b
a










)
(
)
(
a
b
a
b
b
a

 
 







b
a
b
a
a
b
a
a
b
b
b
a












Приклад 2. За допомогою рівносильних перетворень максимально спростити формулу та визначити тип:








c
b
c
a
b
a






16
Розв’язання.








c
b
c
a
b
a




















c
b
c
a
b
a

 
 








c
b
c
a
b
a

 

c
a
b
c
b
c
a
b
a








На першому кроці застосовано до всіх чотирьох імплікацій закон
b
a
b
a



, на другому кроці застосовано двічі закон де Моргана, на третьому кроці опущено дужки за асоціативністю диз’юнкції, четвертий крок одержано із застосуванням законів: поглинання, дистрибутивного диз’юнкції відносно кон’юнкції, виключеного третього та
a
a

 1
Отримана формула, як бачимо, не є тавтологією (т.я. набуває логічного значення 0 на наборі (1,1,0)) і не є суперечністю (т.я. набуває значення 1 коли a=0
або b=0або c=1), отже це нейтральна формула.
Запитання для самоконтролю
1. Які формули алгебри висловлень називають рівносильними?
2. У чому суть ознаки рівносильності?
3. Які властивості має відношення рівносильності?
4. Якою рівносильністю записуються закони де Моргана?
5. Якою рівносильністю записуються закони поглинання?
6. Якими рівносильностями подаються комутативний, асоціативний та дистрибутивний закони алгебри висловлень?
7. Якими рівносильностями подаються закон виключення суперечності та закон виключеного третього?
8. У чому суть законів подвійного заперечення, ідемпотентності, контра позиції?
9. Сформулюйте теорему про заміну?
10. Що таке рівносильне перетворення формули? Які застосування рівносильних перетворень?
ВПРАВИ
1.13Перевірити, чи існує рівносильність, якою визначається: a) асоціативність дії

; b) дистрибутивність дії

відносно дії

; c) дистрибутивність дії

відносно дії

1.14 Довести чи спростувати рівносильність формул алгебри висловлень: a)


b
a
b
a



;

17
b)
a
a
b
a



; c)




c
b
a
c
b
a





; d)

 

c
b
a
c
b
a





; e)




c
a
a
b
a
c
b
a







; f)


c
b
a
c
b
a





(
)
; g)

 







a
b
a
b
a
c
a
c
b
b
a










1.15 Довести основні рівносильності теореми 1.2.2.
1.16 За допомогою рівносильних перетворень максимально спростити наступні формули: a)






b
a
b
a
c
b
c
b







; b)



 

c
a
c
b
a
b
a






; c)



 



c
b
a
c
b
a
c
b
a








; d)





 

c
c
a
c
b
a
b
a







; e)

 

c
c
b
b
a




; f)





 



c
c
a
c
b
a
b
a







1.17 Визначити тип формул за допомогою рівносильних перетворень: a)






c
b
a
c
b
a





; b)


b
b
a


; c)
a
a
b
a
c
a





; d)


c
b
a
c
b
a
c






; e)


b
a
b
a



; f)



 

c
b
a
b
c
a
b






1.18 Перетворити формули на рівносильні, що містять лише задані операції: a)
)
(
x
y
z
x



, логічні операції:

,
; b)
z
y
z
y
x




)
(
, логічні операції:

,
; c)
)
(
z
y
x
y



, логічні операції:

,
; d)
x
y
z
z



, логічні операції:

,

18