Реферат на тему:
Алгебра висловлень
Носієм алгебри висловлень є множина так званих простих висловлень.
Просте (елементарне) висловлення (висловлювання) - це просте твердження, тобто розповідне речення, щодо змісту якого доречно ставити питання про його правильність або неправильність.
Прості висловлення, в яких виражено правильну думку, називатимемо істинними, а ті, що виражають неправильну, - хибними.
Поняття простого (елементарного) висловлення, поняття істинності і хибності належать до первинних невизначальних понять математики, тобто вони не можуть бути означені через інші більш прості терміни та об’єкти, а пояснюються на прикладах, апелюючи до нашої уяви та інтуїції. До таких понять в математиці належать поняття «число», «пряма», «точка», «площина» тощо.
Наведемо декілька прикладів елементарних висловлень:
1) Київ - столиця України.
2) Число 7 є простим.
3) Число 10 більше від числа 3.
4) Усі натуральні числа є простими.
5) Множина всіх простих чисел є скінченною.
Перші три висловлення є істинними, а два останніх - хибними.
У той же час речення «Хай живе математична логіка!» або «Уважно прочитайте весь цей розділ» не є висловленнями.
Розглядаючи висловлення, виходитимо з двох основних припущень:
1) кожне висловлення є або істинним, або хибним (закон виключення третього);
2) жодне висловлення не є одночасно істинним і хибним (закон виключення суперечності).
Приймаючи ці припущення, ми стаємо на точку зору класичної (традиційної) двозначної логіки. У ХХ столітті виникли і продовжують досліджуватись так звані некласичні логіки: багатозначна логіка, інтуїціоністська (конструктивна) логіка, модальна логіка. У подальшому ми додержуватимемося принципів класичної логіки, в рамках якої проводитимуться всі математичні міркування.
Позначатимемо елементарні висловлення малими латинськими літерами: a,b,c,... (можливо, з індексами), а значення висловлень «Iстинно» і «Хибно» - відповідно символами 1 і 0 або I і Х.
Крім того, розглядатимемо так звані змінні висловлення, які позначатимемо латинськими літерами x,y,z,... (можливо, з індексами) і називатимемо також пропозиційними змінними. Після підстановки замість пропозиційної змінної певного елементарного висловлення ця змінна набуде відповідного значення: 0 або 1.
Сигнатура алгебри висловлень традиційно складається з таких операції: заперечення, кон’юнкція, диз’юнкція та імплікація.
У таблиці 1 наведені різні назви та позначення, які використовують для зазначених операцій.
| Назва | Позначення |
| Кон’юнкціяЛогічне множенняЛогічне «І» | Ù&× |
| Диз’юнкціяЛогічне додаванняЛогічне «АБО» | Ú |
| ЗапереченняЛогічне «НІ» | Ø-¢ |
| ІмплікаціяЛогічне слідування | ®É |
Використовуватимемо перші з наведених назв та позначень. Нижче подано таблицю 2, що містить означення цих операцій.
Таблиця 2
| Ù | 0 | 1 | Ú | 0 | 1 | Ø | 0 | 1 | ® | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Застосовуючи до елементарних висловлень і пропозиційних змінних означені операції, діставатимемо складені висловлення, яким відповідатимуть так звані формули або вирази алгебри висловлень. Для запису цих формул, дослідження їхніх властивостей і співвідношень між формулами та висловленнями використовують формальні мови, тобто певні множини слів у деякому алфавіті.
Алфавіт найбільш поширеної формальної мови алгебри висловлень складається з трьох груп символів:
1) символи елементарних висловлень та пропозиційних змінних: a,b,c,... і x,y,z,... (можливо з індексами);
2) символи операцій: Ù,Ú,Ø,® ;
3) допоміжні символи - круглі дужки: ( і ).
З пропозиційних змінних і елементарних висловлень за допомогою операцій і дужок будуються пропозиційні формули або просто формули алгебри висловлень за такими індуктивними правилами:
1) всі пропозиційні змінні та елементарні висловлення є формулами;
2) якщо A і B - формули, то вирази (AÙB), (AÚB), (ØA), (A®B) також є формулами;
3) інших формул, ніж побудовані за правилами 1) і 2), немає.
Традиційно формули алгебри висловлень позначають великими готичними літерами, але для зручності позначатимемо їх великими латинськими літерами.
Кожна формула A зображує форму або схему складеного висловлення: вона перетворюється у висловлення якщо замість її пропозиційних змінних підставити будь-які висловлення. Оскільки кожне з підставлених висловлень має значення 0 або 1, то послідовно обчислюючи значення всіх підформул формули A, одержимо значення формули A на цьому наборі висловлень, яке дорівнюватиме 0 або 1. Підставляючи у формулу A замість її пропозиційних змінних інший набір висловлень, аналогічним чином обчислимо нове значення формули A і т.д. Оскільки кожне з висловлень набору повністю характеризується своїм значенням (істинно або хибно, тобто 1 або 0), то замість пропозиційних змінних у формулу можна підставляти не самі висловлення, а їхні значення - 1 або 0.
Нехай p1,p2,...,pn - це всі пропозиційні змінні, що входять у формулу A; будемо позначати цей факт A(p1,p2,...,pn). Формулі A(p1,p2,...,pn) поставимо у відповідність функцію f (p1,p2,...,pn), що означена на множині Bn (B={0,1}) і приймає значення у множині B, тобто функцію типу Bn®B. Значення функції f на наборі значень a1,a2,...,an її змінних p1,p2,...,pn дорівнює значенню формули A(p1,p2,...,pn) при підстановці в неї замість пропозиційних змінних p1,p2,...,pn значень a1,a2,...,an відповідно.
Зауважимо, що кількість елементів в області визначення функції f дорівнює 2n, тобто |Pr1f |=2n.
Функцію f називають функцією істинності для формули A або відповідного складеного висловлення. Для функції істинності може бути побудована так звана таблиця істинності цієї функції (див.таблицю 3).
Таблиця 3
| p1p2 ...... pn-1 pn | f (p1,p2,...,pn-1,pn) |
| 0 0 ... 0 00 0 ... 0 10 0 ... 1 00 0 ... 1 1.........................1 1 ... 1 01 1 ... 1 1 | f (0,0,...,0,0) f (0,0,...,0,1) f (0,0,...,1,0) f (0,0,...,1,1) ..................... f (1,1,...,1,0) f (1,1,...,1,1) |
Серед формул алгебри висловлень особливе місце займають ті формули A(p1,p2,...,pn), які на всіх наборах (a1,a2,...,an) значень своїх змінних набувають значення 1.
Формула алгебри висловлень A(p1,p2,...,pn) називається тавтологією тоді і тільки тоді, коли їй відповідає функція істинності, яка тотожно дорівнює 1.
Тавтології ще називають тотожно істинними формулами, або законами алгебри висловлень. Аналогом тавтології у природній мові є поняття істинного твердження.
Наведемо приклади деяких важливих тавтологій:
(pÚ(Øp)) (закон виключення третього),
(Ø(pÙ(Øp))) (закон виключення суперечності),
(p®p) (закон тотожності).
Довести, що ці формули є тавтологіями можна за допомогою відповідних таблиць істинності. Той факт, що формула A алгебри висловлень є тавтологією позначають так |=A. Символ |=, як і A належать метамові.
Формула алгебри висловлень A(p1,p2,...,pn), яка набуває значення 0 на всіх наборах (a1,a2,...,an) значень своїх пропозиційних змінних, називається суперечністю, або тотожно хибною формулою.
Формулу, яка не є ні тавтологією, ні суперечністю, називають нейтральною.
Множина всіх формул алгебри висловлень розбивається на тавтології, суперечності та нейтральні формули.
Формула, яка не є суперечністю, називається виконуваною.
Наведемо ряд тверджень, справедливість яких очевидна.
1. Заперечення тавтології є суперечністю і навпаки.
2. Кожна тавтологія є виконуваною формулою (навпаки, взагалі кажучи, ні).
3. Кожна нейтральна формула є виконуваною, але не навпаки.
4. Заперечення виконуваної формули може бути, як виконуваною формулою, так і невиконуваною формулою.
Дві формули A і B алгебри висловлень називаються рівносильними, якщо їм відповідає та сама функція істинності. Рівносильність формул A і B позначають за допомогою знака = (º або «): записують A=B (AºB або A«B).
Очевидно, що відношення рівносильності на множині формул є відношенням еквівалентності, тому часто це відношення називають еквівалентністю.
Наведемо приклади пар рівносильних формул:
(A®B) = ((ØA)ÚB), (Ø(AÚB)) = ((ØA)Ù(ØB)), (Ø(AÙB)) = ((ØA)Ú(ØB)),
(AÙ(BÚC)) = ((AÙB)Ú(AÙC)), (AÚ(BÙC)) = ((AÚB)Ù(AÚC))
тощо.
Ці рівносильності та подібні до них легко перевірити обчисленням таблиць істинності відповідних функцій для лівих і правих частин і порівнюванням цих таблиць.