WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Алгебра висловлень - Реферат

Алгебра висловлень - Реферат


Реферат на тему:
Алгебра висловлень
Носієм алгебри висловлень є множина так званих простих висловлень.
Просте (елементарне) висловлення (висловлювання) - це просте твердження, тобто розповідне речення, щодо змісту якого доречно ставити питання про його правильність або неправильність.
Прості висловлення, в яких виражено правильну думку, називатимемо істинними, а ті, що виражають неправильну, - хибними.
Поняття простого (елементарного) висловлення, поняття істинності і хибності належать до первинних невизначальних понять математики, тобто вони не можуть бути означені через інші більш прості терміни та об'єкти, а пояснюються на прикладах, апелюючи до нашої уяви та інтуїції. До таких понять в математиці належать поняття "число", "пряма", "точка", "площина" тощо.
Наведемо декілька прикладів елементарних висловлень:
1) Київ - столиця України.
2) Число 7 є простим.
3) Число 10 більше від числа 3.
4) Усі натуральні числа є простими.
5) Множина всіх простих чисел є скінченною.
Перші три висловлення є істинними, а два останніх - хибними.
У той же час речення "Хай живе математична логіка!" або "Уважно прочитайте весь цей розділ" не є висловленнями.
Розглядаючи висловлення, виходитимо з двох основних припущень:
1) кожне висловлення є або істинним, або хибним (закон виключення третього);
2) жодне висловлення не є одночасно істинним і хибним (закон виключення суперечності).
Приймаючи ці припущення, ми стаємо на точку зору класичної (традиційної) двозначної логіки. У ХХ столітті виникли і продовжують досліджуватись так звані некласичні логіки: багатозначна логіка, інтуїціоністська (конструктивна) логіка, модальна логіка. У подальшому ми додержуватимемося принципів класичної логіки, в рамках якої проводитимуться всі математичні міркування.
Позначатимемо елементарні висловлення малими латинськими літерами: a,b,c,... (можливо, з індексами), а значення висловлень "Iстинно" і "Хибно" - відповідно символами 1 і 0 або I і Х.
Крім того, розглядатимемо так звані змінні висловлення, які позначатимемо латинськими літерами x,y,z,... (можливо, з індексами) і називатимемо також пропозиційними змінними. Після підстановки замість пропозиційної змінної певного елементарного висловлення ця змінна набуде відповідного значення: 0 або 1.
Сигнатура алгебри висловлень традиційно складається з таких операції: заперечення, кон'юнкція, диз'юнкція та імплікація.
У таблиці 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
p1 p2 ...... pn-1 pn f (p1,p2,...,pn-1,pn)
0 0 ... 0 0
0 0 ... 0 1
0 0 ... 1 0
0 0 ... 1 1
.........................
1 1 ... 1 0
1 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), яка набуває значення
Loading...

 
 

Цікаве