Лекція 1. 2. Висловлення. Логічні операції над висловленнями

План

1. Вступ.

2. Висловлення. Логічні операції над висловленнями.

3. Формули алгебри висловлень.

1. Вступ

Термін ”логіка” - наука про способи доведень й спростувань - походить від грецького logox (логос), що означає ”слово”, ”поняття”, ”смисл”. Поняття ”традиційна або формальна логіка” характеризує науку, яка бере свій початок від Аристотеля, котра вивчає форми й закони мислення, а також методи, за допомогою яких люди в дійсності роблять висновки, встановлюють зв’язок логічних форм з мовою. Поява логічних форм і категорій, формування законів мислення - це результат загальнолюдської практики. Довготривала практична діяльність людини в процесі пізнання оточуючої дійсності викристалізувала фігури й закони логіки. Логіка вивчає те загальне, що зв’язує міркування в їх русі до пізнання істини. Вона є наукою про закони і форми правильного міркування. Логіка вивчає форми міркувань, відволікаючись від їх конкретного змісту; установлює що із чого випливає.

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

Засновником логіки як науки є Аристотель (384-322 рр. до н.е.). Він вперше розробив теорію дедукції, тобто теорію логічного виведення. Аристотель звернув увагу на те, що в міркуваннях ми із одних тверджень виводимо інші, виходячи не із конкретного змісту тверджень, а із визначеного зв’язку між їх формами й структурами. На протязі багатьох віків різними філософами удосконалювалася й змінювалася логіка Аристотеля. Це був перший (доматематичний) етап розвитку формальної логіки. другий етап пов’язаний з застосуванням в логіці математичних методів, початок якому поклав німецький філософ і математик Г. Лейбніц (1646-1716). Він намагався побудувати універсальну мову, за допомогою якої можна було б розв’язувати суперечки між людьми, а потім і взагалі всі ”ідеї замінити численнями”. Важливий період становлення математичної логіки починається з робіт англійського математика й логіка Джорджа Буля (1815-1864) ”Математичний аналіз логіки” (1847) та ”Дослідження законів мислення” (1854). Ним була побудована алгебра логіки. В цей період вона сформувалася як алгебра висловлювань й була значно розвинута в роботах шотландського логіка А. де Моргана (1806-1871), англійського логіка У. Джевонса (1835-1882), американського логіка Ч. Пірса (1839-1914), німецького алгебраїста і логіка Е. Шрьодера (1841-1902), російського математика й логіка П.С. Порецького (1846-1907). Утворення алгебри логіки стало заключним етапом у розвитку формальної логіки: алгебра логіки поставила й розв’язала в самому загальному вигляді ті задачі, які розглядалися в арістотелевій логіці.

Значним поштовхом до нового періоду розвитку математичної логіки стала побудова в першій половині ХІХ ст. російським математиком М.І. Лобачевським (1792-1856) і незалежно від нього угорським математиком Я. Бояі (1802-1860) неевклідової геометрії. Крім того, створення аналізу нескінченно малих привело до необхідності обґрунтування числа як фундаментального поняття всієї математики. Завершили картину парадокси, виявлені в кінці ХІХ ст. в теорії множин: вони показали, що труднощі обґрунтування математики є труднощами логічного й методологічного характеру. В ході розвитку математичної логіки сформувалися три напрямки обґрунтування математики.

Засновником одного із напрямків - логіцизму - став німецький математик і логік Г. Фреге (1848-1925). Він намагався всю математику обґрунтувати через логіку. Ним і незалежно від нього Ч. Пірсом були введені в мову логіки предикати, предметні змінні й квантори, що дало можливість застосувати цю мову до питань обґрунтування математики. Задачу аксіоматичної побудови арифметики ставив перед собою італійський математик Дж. Пеано (1858-1932). Зведення чистої математики до логіки продовжили англійські математики Б. Рассел (1872-1970) і А. Уайтхед (1861-1947). Даний напрямок не увінчався успіхом, проте був створений багатий логічний апарат, без якого математична логіка не змогла б оформитися як повноцінна математична дисципліна.

Німецький математик Д. Гільберт (1862-1943) запропонував свій шлях подолання труднощів в основах математики, базуючись на застосуванні аксіоматичного методу, за допомогою якого всі математичні твердження записуються у вигляді логічних формул, деякі з яких виділяються в значенні аксіом, а інші із них виводяться. Цей напрямок отримав назву формалізм. Відкриття в 1930-1931рр. австрійським математиком К. Геделем (1906-1978) неповноти формалізованої арифметики показало обмеженість гільбертовської програми обґрунтування математики. Проте роботи Гільберта і його послідовників привели до глибокої розробки аксіоматичного методу й усвідомленню його фундаментальної ролі в математиці.

Представники напрямку, який виник на початку ХХ ст. у працях готландського математика Л. Брауєра (1881-1966) й одержав назву інтуїціонізму, запропонували відмовитися від розгляду нескінченних множин як завершених сукупностей, а також від закону виключення третього. Ними признавалися лише ті доведення, які конструктивно будували той чи інший об’єкт, і не признавалися чисті доведення існування.

ХХ ст. - час великого розвитку математичної логіки, формування багатьох її нових розділів: побудовані різні аксіоматичні теорії множин; на базі математичної логіки сформована теорія алгоритмів, за допомогою якої були вироблені декілька формалізацій поняття алгоритму. Методи теорії алгоритмів стали проникати в інші розділи математичної логіки і в суміжні математичні дисципліни. В інші розділи математики стала проникати й сама математична логіка. Прикладом може бути теорія моделей, котра утворилася на межі сучасної алгебри й логіки. Значний вклад у розвиток математичної логіки внесли математики І. І. Жегалкін, А.М. Колмогоров, П.С. Новіков, А.А. Макаров, А.І. Мальцев, С.А. Яновська. Ідеї й методи математичної логіки глибоко проникли в процес конструювання й створення ЕОМ, в програмування, інформатику, обчислювальну математику, структурну лінгвістику. Ці методи використовуються як при фізичному конструюванні й створенні комп’ютерів, так і при створенні математичного забезпечення до них. В основі багатьох мов програмування лежить теорія алгоритмів, теорія формальних систем, логіка предикатів. Наприклад, назва мови ПРОЛОГ означає скорочення від слів ”ПРОграмування ЛОГічне”. Крім того, синтез логіки й комп’ютерів привів до виникнення баз даних і експертних систем, що стало важливим етапом на шляху до створення штучного інтелекту.

2. Висловлення. Логічні операції над висловленнями.

Предметом дослідження алгебри висловлень є висловлення. Під висловленням розуміють речення, яке або істинне, або хибне. Висловлення не може одночасно бути істинним і хибним.

Далі будемо вважати, що є початкова сукупність найпростіших висловлень, які називаються елементарними, про кожне із яких точно відомо, істинне воно чи хибне. Конкретні висловлення позначатимемо буквами латинського алфавіту A, B, C, D, … або тими ж буквами з індексами внизу.

Позначивши істинне висловлення символом 1, а хибне ― 0, уведемо функцію λ, задану на сукупності всіх висловлень, котра приймає значення на двохелементній множині , за наступним правилом:

Функція λ називається функцією істинності, а значення λ(Р) - логічним значенням або значенням істинності висловлення Р.

Із елементарних висловлень за допомогою логічних зв’язок утворюються складні висловлення.

Розглянемо логічні операції над висловленнями.

Заперечення висловлення. Запереченням висловлення Р називається висловлення Р (читається: ”не Р ”), яке істинне, якщо висловлення Р хибне, і хибне, якщо Р істинне.

Кон’юнкція двох висловлень. Кон’юнкцією двох висловлень P і Q називається висловлення, яке позначається або P & Q (читається: ” P і Q ”), котре істинне тоді й тільки тоді, коли істинні висловлення P і Q, й хибне в усіх інших випадках.

Диз’юнкція двох висловлень. Диз’юнкцією двох висловлень P і Q називається висловлення, яке позначається (читається “ P або Q ”), котре істинне в тих випадках, коли принаймні одне із висловлень P або Q істинне, й хибне в єдиному випадку, коли обидва висловлення P і Q хибні.

Імплікація двох висловлень. Імплікацією двох висловлень P і Q називається висловлення (читається: “якщо P, то Q ”, або “із P випливає Q ”, або “ P достатньо для Q ”, або ” Q необхідно для Р ”), яке хибне в єдиному випадку, коли висловлення P істинне, а Q - хибне, а в усіх інших випадках - істинне.

У висловленні висловлення Р називається посилкою або антецедентом, а висловлення Q - наслідком або консеквентом.

Еквівалентність двох висловлень. Еквівалентністю двох висловлень P і Q називається висловлення (читається: “ P еквівалентно Q ”, або “ P необхідно й достатньо для Q ”, або “ P тоді й тільки тоді, коли Q ”, яке істинне лише в тому випадку, коли одночасно обидва висловлення P і Q або істинні, або хибні.

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

λ(Р)	λ(Q)	λ(Р)	λ( )	λ( )	λ( )	λ( )

Якщо ввести наступні операції над символами 0 и 1: 0 = 1, 1 = 0, , , , , , , , , , , , то матимемо

, , , , .