Коли сформувалася математична логіка. Основи математичної логіки

Інші розділи

МАТЕМАТИЧНА ЛОГІКА, дедуктивна логіка, що включає математичні методидослідження методів міркувань (висновків); математична теорія дедуктивних методів міркувань. Математичною логікоюназивають також логіку, якою користуються в математиці.

Важливу роль математичної логіці грають поняття дедуктивної теорії та обчислення.Обчисленням називається сукупність правил виведення, що дозволяють вважати деякі формули, що виводяться. Правила виведення поділяються на два класи. Одні їх безпосередньо кваліфікують деякі формули як виведені. Такі правила висновку прийнято називатиаксіомами . Інші дозволяють вважати виведеними формули, синтаксично пов'язані деяким заздалегідь визначеним способом з кінцевими наборами формул, що виводяться. Широко застосовуваним правилом другого типу є правило modus ponens: якщо виводиться формула і, то виводиться і формула.

Ставлення обчислень до семантики виражається поняттями семантичної придатності та семантичної повноти обчислення. Обчислення І називається семантично придатним для мови Я, якщо будь-яка виводиться в І формула мови Я є вірною. Аналогічно, обчислення І називається семантично повним у мові Я, якщо будь-яка вірна формула мови Я виводиться в І.

Математична логіка вивчає логічні зв'язкита відносини, що лежать в основі логічного (дедуктивного) висновку, з використанням мови математики.

Багато з мов, що розглядаються в математичній логіці, мають семантично повні і семантично придатні обчислення. Зокрема, відомий результат К. Геделя про те, що так зване класичне літочислення предикатів є семантично повним та семантично придатним для мови класичної логіки предикатів першого порядку. З іншого боку, є чимало мов, для яких побудова семантично повного та семантично придатного обчислення неможлива. У цій галузі класичним результатом є теорема Геделя про неповноту, що стверджує неможливість семантично повного та семантично придатного обчислення для мови формальної арифметики.

На практиці безліч елементарних логічних операцій є обов'язковою частиною набору інструкцій всіх сучасних мікропроцесорів і відповідно входить до мов програмування. Це є одним з найважливіших практичних додатків методів математичної логіки, що вивчаються в сучасних підручникахінформатики.

Розділи математичної логіки

Алгебра логіки


Логіка висловлювань


Теорія доказів


Теорія моделей

Логіка висловлювань (чи пропозиційна логіка від англ. propositional logic, чи обчислення висловлювань) - це формальна теорія, основним об'єктом якої є поняття логічного висловлювання. З погляду виразності, її можна охарактеризувати як класичну логіку нульового порядку.

Незважаючи на свою важливість та широку сферу застосування, логіка висловлювань є найпростішою логікоюта має дуже обмежені засоби для дослідження суджень

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

Базовими елементами, якими оперує алгебра логіки, є висловлювання. Висловлювання будуються над безліччю , над елементами якого визначено три операції:

Заперечення (унарна операція),


Кон'юнкція (бінарна),


Диз'юнкція (бінарна),

а також константи - логічний нуль 0 та логічна одиниця 1.

Теорія ймовірності - розділ математики, що вивчає випадкові події їх властивості та операції з них.

У теорії ймовірностей вивчаються, ті випадкові події, які можуть бути відтворені в одних і тих же умовах і такі властивості: в результаті експерименту, за умови S подія A може статися з певною ймовірність p.

Основними поняттями теорії ймовірності є: подія, ймовірність, випадкова подія, Довільне явище, математичне очікування, дисперсія, функція розподілу, імовірнісний простір.

Як наука теорія ймовірностей виникає у середині 17 століття. Перші роботи з'являються у зв'язку з підрахунком ймовірностей в азартних іграх. Досліджуючи прогнозування виграшу при киданні кісток,Блез Паскаль та П'єр ФермаУ своєму листуванні 1654 року відкрили перші ймовірні закономірності. Зокрема в цьому листуванні вони дійшли до поняття математичного очікування і теорем множення та складання ймовірностей. В 1657 ці результати були наведені в книзі Х. Гюйгенса «Про розрахунки в азартних іграх», яка є першим трактатом з теорії ймовірностей.

Великих успіхів у теорії ймовірностей досягнувЯків Бернуллі : він встановив закон великих чиселу найпростішому випадку, сформулював багато понять сучасної теорії ймовірностей. Їм була написана монографія з теорії ймовірностей, яка була видана посмертно в 1713, під назвою «Мистецтво припущень».

У першій половині 19 століття теорія ймовірностей починає застосовуватися теорії помилок спостережень. В цей час були доведенітеорема Муавра - Лапласа (1812) та теорема Пуассона(1837), є першими граничними теоремами. Лаплас розширив та систематизував математичні основи теорії ймовірностей. Гаус і Лежандр розробили метод найменших квадратів.

У другій половині 19 століття більшість відкриттів у теорії ймовірності було зроблено російськими вченимиП. Л. Чебишевимта його учням та А. М. Ляпуновим та А.А Марковим.У 1867 році Чебишев сформулював і досить просто довів закон великих чисел за загальних умов. У 1887 він же вперше сформулював та запропонував метод вирішення центральної граничної теореми для сум незалежних випадкових величин. У 1901 році ця теорема була доведена Ляпуновим за більш загальних умов. Марков у 1907 році вперше розглянув схему випробувань пов'язаних у ціп, тим самим поклавши основу теорії Марківських ланцюгів. Також він зробив великий внесок у дослідження, що стосуються теорії великих чисел і центральної граничної теореми.

На початку 20 століття відбувається розширення кола застосування теорії ймовірностей, створюються системи строго математичного обґрунтування та нові методи теорії ймовірностей. У цей період завдяки працямАндрія Миколайовича Колмогороватеорії ймовірностей набуває сучасного вигляду.

У 1926 році, будучи аспірантом, Колмогоров отримує необхідні та достатні умови, за яких має місце закон великих чисел. У 1933 у своїй роботі «Основні поняття теорії ймовірностей» Колмогоров запроваджує аксіоматику теорії ймовірностей, яка загальновизнана найкращою.

Математичний апарат теорії ймовірності широко використовується в науці та техніці. Зокрема в астрономії до розрахунку орбіт комет використовується метод найменших квадратів. У медицині в оцінці ефективності методів лікування як і використовується теорія ймовірності.

/ БДЕ Математика /

Дедукція

Пам'ятаєте, Шерлок Холмс постійно стверджував про свої дедуктивні здібності? То що таке дедукція?

Дедукція (лат. deductio - виведення)- така форма мислення, коли нова думкавиводиться чисто логічним шляхом з попередніх думок. Така послідовність думок називається висновком, а кожен компонент цього висновку є раніше доведеною думкою, або аксіомою, або гіпотезою. Остання думка цього висновку називається укладанням.

Дедуктивний висновок, що є предметом традиційної логіки, застосовується нами кожного разу, коли потрібно розглянути якесь явище на підставі вже відомого нам загального стану і вивести щодо цього явища необхідний висновок. Нам відомий, наприклад, такий конкретний факт - “ дана площинаперетинає кулю” і загальне правило щодо всіх площин, що перетинають кулю, - “будь-який переріз кулі площиною є коло”. Застосовуючи це загальне правило до конкретного факту, кожен правильно мисляча людина необхідно дійти одного й тому висновку: “значить дана площина є коло”.

Структура дедуктивного висновку та примусовий характер його правилвідобразили найпоширеніші відносини між предметами матеріального світу: відносини роду, виду та особини, тобто загального, приватного та одиничного: те, що притаманне всім видам даного роду, то властиво і будь-якому виду; те, що притаманне всім особинам роду, то притаманне і кожній особині.

Вперше теорія дедукції була розроблена Аристотелем. Він з'ясував вимоги, яким мають відповідати окремі думки, що входять до складу дедуктивного висновку, визначив значення термінів та розкрив правила деяких видів дедуктивних висновків. Позитивною стороноюарістотелівського вчення про дедукцію є те, що в ньому відобразилися реальні закономірності об'єктивного світу.

Під терміном “дедукція” у вузькому значенні слова розуміють таке:
1) Метод дослідження, який полягає в наступному: для того, щоб отримати нове знання про предмет чи групу однорідних предметів, треба, по-перше знайти найближчий рід, куди входять ці предмети, і, по-друге, застосувати до них відповідний закон, властивий всьому даному роду предметів. Дедуктивний спосіб грає величезну роль математиці. Відомо, що всі теореми виводяться логічним шляхом за допомогою невеликої дедукції. кінцевого числавихідних початків, званих аксіомами.
2) Форма викладу матеріалу у книзі, лекції, доповіді, бесіді, коли від загальних положень, правил, законів йдуть до менш загальним положенням, правил, законів.
Цей спосіб дозволяє ставити формальні аксіоматичні теорії.
2.Завдання тільки аксіом
У цьому випадку правила виведення вважаються загальновідомими, тому задаються лише аксіоми. Тому при такій побудові теорем кажуть, що напівформальна аксіоматична теорія.
3.Завдання лише правил виведення
Даний спосіб побудови теорем ґрунтується на завданні лише правил виведення, оскільки безліч аксіом порожня. Виходячи з цього, теорія, задана таким чином, є окремий випадокформальної теорії Пізніше цей різновид став називатися теорією природного висновку.

До основних властивостей дедуктивних теорій відносяться:
1. Суперечливість
Суперечливою називається теорія, в якій безліч теорем покриває безліч формул.
2. Повнота
Повною називається теорія, в якій для будь-якої формули F виводиться або сама F, або її заперечення -F.
3. Незалежність аксіом
Коли окрему аксіому теорії не можна вивести з інших аксіом, її називають незалежною. Система аксіом називається незалежною лише тому випадку, якщо кожна аксіома у ній незалежна.
4. Дозвілість
Коли теоретично існує ефективний алгоритм, що дозволяє визначити кількість кроків, що доводять теорему, теорія називається розв'язною. Наприклад, логіка висловлювань, логіка першого порядку (числення предикатів), формальна арифметика(теорія S).

МІНІСТЕРСТВО ОСВІТИ І НАУКИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ

Федеральне державне бюджетне освітня установавищого професійної освіти

«ЛИПЕЦЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ»

Факультет фізико-математичних та комп'ютерних наук

Кафедра математики

Контрольна робота на тему:

"Історія розвитку математичної логіки"

Виконала:

Студентка 2 курсу

групи МФ-2

Понамарьова Вікторія Сергіївна

Науковий керівник:

к. ф.-м. н., доцент

Єршова Олександра Олексіївна

Липецьк, 2014

Вступ

§1. Історія виникнення математичної логіки

§2. Застосування математичної логіки

§3. Математична логіка у техніці

§4. Математична логіка у криптографії

§5. Математична логіка у програмуванні

Висновок

Список використаної літератури

математичне позначення криптографія програмування

Вступ

Логіка<#"center">§1. Історія виникнення математичної логіки

Математична логіка тісно пов'язана з логікою та завдячує їй своїм виникненням. Основи логіки, науки про закони та форми людського мислення(звідси одна з її назв - формальна логіка), були закладені найбільшим давньогрецьким філософом Аристотелем (384-322 рр. до н. е..), який у своїх трактатах докладно досліджував термінологію логіки, докладно розібрав теорію висновків і доказів, описав ряд логічних , сформулював основні закони мислення, у тому числі закони протиріччя та виключення третього. Внесок Арістотеля в логіку дуже великий, недарма інша її назва - Арістотельова логіка. Ще сам Аристотель зауважив, що між створеною ним наукою та математикою (тоді вона називалася арифметикою) багато спільного. Він намагався поєднати ці дві науки, а саме звести міркування, або, вірніше, висновок, до обчислення на підставі вихідних положень. В одному зі своїх трактатів Арістотель впритул наблизився до одного з розділів математичної логіки – теорії доказів.

Надалі багато філософів і математиків розвивали окремі положення логіки і іноді навіть намічали контури сучасного обчислення висловлювань, але найближче до створення математичної логіки підійшов вже в другій половині XVII століття видатний німецький вчений Готфрід Вільгельм Лейбніц (1646 - 1716), що вказав шляхи «Зі словесного царства, повного невизначеностей, в царство математики, де відносини між об'єктами або висловлюваннями визначаються точно» . Лейбніц сподівався навіть, що в майбутньому філософи, замість безплідно сперечатися, братимуть папір і обчислюватимуть, хто з них правий. При цьому у своїх роботах Лейбніц торкався і двійкової системи числення.

Слід зазначити, що ідея використання двох символів для кодування інформації дуже стара. Австралійські аборигени вважали двійками, деякі племена мисливців-збирачів Нової Гвінеї та Південної Америкитеж користувалися двійковою системою рахунку. У деяких африканських племенах передають повідомлення з допомогою барабанів як комбінацій дзвінких і глухих ударів. Знайомий всім приклад двосимвольного кодування - абетка Морзе, де літери алфавіту представлені певними поєднаннямиточок та тире.

Після Лейбніца дослідження в цій галузі вели багато видатних учених, проте справжній успіх прийшов тут до англійського математика-самоучки Джорджа Буля (1815-1864), цілеспрямованість якого не знала кордонів. Матеріальне становище батьків Джорджа (батько якого був шевським майстром) дозволило йому закінчити лише початкову школудля бідняків. Згодом Буль, змінивши кілька професій, відкрив маленьку школу, де сам викладав. Він багато часу приділяв самоосвіті і незабаром захопився ідеями символічної логіки. В 1847 Буль опублікував статтю «Математичний аналіз логіки, або Досвід обчислення дедуктивних висновків», а в 1854 з'явився головний його праця «Дослідження законів мислення, на яких засновані математичні теоріїлогіки та ймовірностей».

Буль винайшов своєрідну алгебру - систему позначень і правил, що застосовується до різноманітних об'єктів, від чисел та букв до речень. Користуючись цією системою, він міг закодувати висловлювання (ствердження, істинність чи хибність яких потрібно довести) за допомогою символів своєї мови, а потім маніпулювати ними, подібно до того, як у математиці маніпулюють числами. Основними операціями булевої алгебри є кон'юнкція (І), диз'юнкція (АБО) та заперечення (НЕ).

Через деякий час стало зрозуміло, що система Буля добре підходить для опису електричних схем перемикання. Струм у ланцюгу може або протікати, або бути відсутнім, подібно до того, як твердження може бути або істинним, або помилковим. А ще через кілька десятиліть, уже в XX столітті, вчені об'єднали створений Джорджем Булем математичний апаратз двійковою системою числення, заклавши цим основи для розробки цифрового електронного комп'ютера.

Окремі положення робіт Буля тією чи іншою мірою торкалися і до, і після нього іншими математиками та логіками. Однак сьогодні в цій галузі саме праці Джорджа Буля зараховуються до математичної класики, а сам він по праву вважається засновником математичної логіки і тим більше найважливіших її розділів – алгебри логіки (бульової алгебри) та алгебри висловлювань.

Великий внесок у розвиток логіки зробили і російські вчені П.С. Порецький (1846-1907), І.І. Жегалкін (1869-1947).

У XX столітті величезну роль розвитку математичної логіки зіграв Д. Гільберт (1862-1943), який запропонував програму формалізації математики, пов'язану з розробкою підстав самої математики. Нарешті, в останні десятиліття XX століття бурхливий розвиток математичної логіки було обумовлено розвитком теорії алгоритмів та алгоритмічних мов, теорії автоматів, теорії графів (С.К. Кліні, А. Черч, А.А Марков, П.С. Новіков, Гегель та багато інші).

Гегель (1770-1831) дуже іронічно відгукувався закон протиріччя і закон виключеного третього. Останній він представляв, зокрема, у такій формі: "Дух є зеленим або не є зеленим", і ставив "підступне" питання: яке з цих двох тверджень істинно? Відповідь це питання не становить, проте, труднощів. Жоден із двох тверджень: "Дух зелений" і "Дух не зелений" не є істинним, оскільки обидва вони безглузді. Закон виключеного третього докладемо лише до осмислених висловлювань. Тільки вони можуть бути істинними чи хибними. Безглузде ж не істинно і хибно. Гегелівська критика логічних законів спиралася, як це нерідко буває, на надання їм того сенсу, якого вони не мають, і приписування їм тих функцій, яких вони не мають відношення. Випадок із критикою закону виключеного третього – один із прикладів такого підходу. Критика закону виключеного третього (Л.Бауер) призвела до створення нового напряму у логіці – інтуїціоністської логіки. В останній не приймається цей закон і відкидаються всі способи міркування, які з ним пов'язані. Серед відкинутих, наприклад, виявляється доказ шляхом приведення до суперечності чи абсурду.

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

Висновок: не можна ухилятися від визнання істинним одного з двох, що суперечать один одному, висловлюй і шукати щось третє між ними.

Результат застосування: досягається однозначність логічного мислення.

Четвертий закон - закон достатньої підстави

Формулювання: всяка справжня думка має достатню основу.

Коментар: Цей закон фактично заявляє те, що всі думки, які можна пояснити, вважаються істинними, а ті які пояснити не можна - хибними. У логіці висловлювань цей закон формули немає, оскільки він має змістовний характер. На цьому варто зупинитися докладніше:

Достатньою, тобто дійсною, невигаданою основою наших думок може бути індивідуальна практика. Справді, істинність деяких суджень підтверджується шляхом їхнього безпосереднього зіставлення з фактами дійсності (Приклад: "[Істинно, що] йде дощ", "[Є брехнею те, що]Я був у Акапулько"). Але особистий досвід обмежений. Тож у реальної діяльності завжди доводиться спиратися досвід інших людей. Завдяки розвитку наукових знань суб'єкт використовує як підстави своїх думок досвід попередників, закріплений у законах і аксіомах науки, у принципах і положеннях, що у будь-якій галузі людської діяльності. Для підтвердження будь-якого окремого випадку немає необхідності звертатися до його практичної перевірки, доводити його за допомогою особистого досвіду. Якщо, наприклад, мені відомий закон Архімеда, то зовсім не обов'язково шукати ванну з водою, щоб, помістивши туди предмет, з'ясувати, скільки він втратив у вазі. Закон Архімеда буде достатньою підставою для підтвердження цього окремого випадку.

Метою науки не лише здобування знання, а й його передача. Саме тому неприпустимі жодні логічні огріхи у формальному поданні вже здобутого знання. Таким чином – знання має бути логічно контрольованим. Саме це оптимально для його збереження, передачі та розвитку. І саме тому наукове знання як сукупність вже доведених логічних речень, може бути основою наступних доказових міркувань.

Закон достатньої підстави фактично зводиться до наступної вимоги: "будь-яке судження, перш ніж бути прийнятим за істину, має бути обґрунтовано". Таким чином, із цього закону випливає, що при правильному міркуванні ніщо не повинно прийматися просто так, на віру. У кожному разі кожного твердження слід зазначати підстави, з яких воно вважається істинним. Як бачимо - закон достатньої підстави спочатку виступає, як методологічний принцип, Що забезпечує здатність мислення постачати підстави для подальших міркувань. Адже все, що вже доведено коректно, можна покласти в основу наступним доказам.

Висновок: достатньою підставою будь-якої думки може бути будь-яка інша, вже перевірена і визнана істинною думка, з якої випливає істинність цієї думки.

Результат застосування: Закон забезпечує обґрунтованість мислення. В усіх випадках, коли ми стверджуємо щось, ми маємо довести свою правоту, тобто. навести достатні підстави, що підтверджують істинність наших думок.

§2. Застосування математичної логіки

Об'єднання математико-логічної установки з іншими математичними підходами, передусім з вероятностно-статистическими ідеями і методами - і натомість глибокого інтересу до обчислювальних приладів, - багато в чому визначальним у формуванні задуму кібернетики, як комплексного наукового напрями, має своїм предметом процеси.

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

Інформатика – це наука, яка вивчає комп'ютер, а також взаємодію комп'ютера з людиною.

Будівництво логічних машин – цікава глава історії логіки та кібернетики. У ній відображені перші проекти створення штучного розуму та перші суперечки щодо можливості цього. Ідея логічних машин з'явилася в 13 столітті в іспанського схоластика Раймунда Луллія, розглядалася потім Лейбніцем і набула нового розвитку в 19 столітті, після виникнення математичної логіки. У 1870 році англійський філософ та економіст Вільям Стенлі Джевонс побудував у Манчестері логічне піаніно , яке витягало з записів алгебри посилок слідства, виділяючи допустимі комбінації термінів. Це називають також розкладанням висловлювань конституанти. Важливо відзначити можливість практичного застосування логічної машини на вирішення складних логічних завдань.

Сучасні універсальні обчислювальні машиниє водночас логічними машинами. Саме запровадження логічних операцій зробило їх такими гнучкими; воно ж дозволяє їм моделювати міркування. Таким чином, арифметична гілка розумних автоматів поєдналися з логічною. У 20-ті роки, однак, формальна логіка здавалася надто абстрактною про метафізичну для додатку до життя. Тим часом, вже тоді можна було передбачити впровадження логічних обчислень у техніку.

Математична логіка полегшує механізацію розумової праці. Нинішні машини виконують набагато складніші логічні операції, ніж скромні прототипи початку століття.

Проблема штучного розуму складна та багатогранна. Ймовірно, не помилимося, якщо скажемо, що остаточні межі механізації думки можна встановити лише експериментальним шляхом. Зауважимо ще, що у сучасної кібернетики обговорюється можливість моделювання як формальних, а й змістовних розумових процесів.

§3.Математичналогікавтехніці

Роль логічної обробки бінарних даних на сучасному етапірозвитку обчислювальної технікизначно зросла. Це пов'язано, насамперед, зі створенням технічних систем. реалізують у тому чи іншому вигляді технології отримання та накопичення знань, моделювання окремих інтелектуальних функцій людини. Ядром таких систем є потужні ЕОМ та обчислювальні комплекси. Крім того, існує великий клас прикладних завдань, які можна звести до вирішення логічних завдань, наприклад, обробка та синтез зображень, транспортні завдання. Необхідна продуктивність обчислювальних засобів досягається шляхом розпаралелювання та конвеєризації обчислювальних процесів. Це реалізується, як правило, на основі надвеликих інтегральних схем (НВІС). Однак технологія НВІС та їх структура пред'являє низку специфічних вимог до алгоритмів, а саме: регулярність, паралельно - потокова організація обчислень, надлінійна операційна складність (багаторазове використання кожного елемента вхідних даних), локальність зв'язків обчислень, двомірність простору реалізації обчислень. Ці вимоги зумовлюють необхідність вирішення проблеми ефективного занурення алгоритму в обчислювальне середовище, або, як заведено говорити, - відображення алгоритму в архітектуру обчислювальних засобів. Нині доведено помилковість раніше поширених поглядів, які у тому, що перехід на паралельно-конвеєрні архітектури ЕОМ вимагатимуть лише невеликий модифікації відомих алгоритмів. Виявилося, що паралелізм і конвеєризація обчислювальних процесів потребує розробки нових алгоритмів навіть для тих завдань, для яких існували добре вивчені та апробовані методи та алгоритми вирішення, але орієнтовані на послідовний принцип реалізації. За прогнозами фахівців, найближчим десятиліттям слід очікувати появи нових концепцій побудови обчислювальних засобів. Підставою для прогнозів є результати перспективних досліджень, що проводяться в даний час, зокрема, в галузі біочипів та органічних перемикаючих елементів. Деякі напрями ставлять за мету створення схем у вигляді шарів органічних молекул і плівок з високорозвиненою структурою. Це дозволить, на думку дослідників, вирощувати комп'ютери на основі генної інженеріїта посилити аналогію між елементами технічних системта клітинами мозку. Тим самим реальні обриси набувають нейрокомп'ютерів, які імітують інтелектуальні функції біологічних об'єктів, у тому числі людини. Очевидно, молекулярна електроніка стане основою створення ЕОМ шостого покоління. Все це об'єктивно зумовлює інтенсивні роботи з методів синтезів алгоритмів обробки логічних даних та їх ефективного занурення в операційне середовище бінарних елементів. Очевидно, що бінарні елементи та бінарні дані найбільш повно відповідають один одному в плані представлення та обробки останніх на таких елементах, якщо їх розглядати окремо. Справді, наприклад, алгебра логіки над числами (0,1) реалізується на бінарному елементі повному використаннійого операційний ресурс. Іншими словами, порушується питання про ефективність, а іноді взагалі можливості реалізації даного алгоритму на такій мережі (структурі). У цьому полягає суть занурення алгоритму структуру.

§4. Математична логіка у криптографії

Криптографія вивчає методи пересилання повідомлень у замаскованому вигляді, за яких лише намічені відправником одержувачі можуть видалити маскування та прочитати повідомлення. Загальна схема захисту інформації представлена ​​на малюнку 2. Етап кодування від помилок заснований на внесенні в передане повідомлення надлишку інформації, достатньої для подолання перешкод лінії зв'язку. Наприклад, припустимо, передається послідовність символів типу 0і 1. При цьому в мережі зв'язку з певною ймовірністю можуть відбуватися помилки прийому сигналу 0 замість сигналу 1або навпаки, тоді кодер на кожен символ ai повідомлення передає п'ятьма імпульсами 00000 якщо ai -0 і навпаки. На приймальному кінці послідовність імпульсів, що приймається, розбивається по п'ять імпульсів, звана блоками. Якщо прийнятому блоці міститься 2 і менше імпульсу 0, то приймається рішення про те, що передавався символ ai-1. Таким чином, вихідна ймовірність помилки буде значно знижена. Елегантніші методи кодування, які при достатньої надійності дозволяють вносити не такий великий надлишок інформації. Для вираження інформації потрібно ввести деякий алфавіт, з якого складатиметься повідомлення (кінцеві впорядковані множини з цих символів). Позначимо через A – потужність обраного алфавіту. Будемо також вважати, що всі множини інформації або, що те саме, безліч всіляких повідомлень звичайно. Як міра інформації в повідомленні даної довжини можна взяти log 2від числа всіляких повідомлень звісно. Тоді обсяг інформації, що падає на символ алфавіту X=log 2a. Далі маємо справу зі словами довгою S, тоді всього таких слів буде N=AS (декартова S- ступінь алфавіту), а отже, кількість інформації в слові Y=Log 2N=Log 2As = SX. Левову частку криптоаналізу становлять методи, побудовані на ймовірнісному аналізі криптограми та пропонованої вихідної мови. Оскільки будь-яка звичайна мова має надлишок інформації, причому нерівномірно розміщених у словах, то літери алфавіту цієї мови можуть мати стійкі приватні характеристики. Наприклад, в англійській мові - це літера, що часто повторює e Крім того, частотними характеристиками можуть бути буквосполучення та їх комбінації. Загальна схема криптосистеми з секретним ключем зображена малюнку 3. Тут Х - відкритий текст, Y- шифр тексту, K - ключ шифру, R - рандомизирующая послідовність.

§5.Математичналогікавпрограмування

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

Поняття функції було перенесено до мов програмування. У мові програмування, зазвичай, передбачено ряд вбудованих функцій, наприклад sin, cos, sqrt тощо. Крім того, програміст має можливість визначати свої власні функції. Вони можуть працювати не тільки з речовими числами, Але й з різними типами даних, що включають зазвичай integer (ціле), real (речове), boolean (булевское), character (рядкове). Вони можуть працювати зі структурами. У мовах Паскаль, Алгол=68 і ПЛ/1 є, наприклад, типи records (записи), arrays (масиви), lists (списки), files of records (файли, що з записів), а значеннями функцій може бути покажчики цих структур . Усе це узгоджено з поняттям області визначення, поза якою функцію не визначено. У мовах програмування ця область задана зазвичай вказівкою типу даних, що є деяким безліччю величин. Так, у Паскалі компілятор повинен стежити, щоб ніяка функція не застосовувалася до величини невідповідного типу, яка б вийти межі області визначення функції.

Функція багатьох аргументів. Тепер потрібно узагальнити визначення, щоб охопити функції багатьох аргументів. Для цього зберемо n аргументів упорядкований набір, який розглядатимемо як один аргумент. Візьмемо функцію віднімання diff(x.y). Трактується її як відображення пар<х,у>у цілі числа. У вигляді безлічі впорядкованих пар її можна записати так: diff = (<<5,3>, 2>. <<6,3>, 3>, <<4,5>, -1>...) Якби натомість у нас була функція чотирьох аргументів h(x,y,z,w), то використали б відображення, визначене на четвірках . Цей прийом використовується у програмуванні. Якщо необхідно зменшити кількість аргументів процедури або функції (причому всі вони мають один і той же тип), то у Фортрані можна записати ці значення масив і передати як параметр цей масив, а не окремі значення. У більш загальному випадку(наприклад, у Паскалі), коли аргументам дозволяється мати різні типи, можна передати як параметр запис і зберігати значення у вигляді окремих компонент цього запису. Насправді набір, що складається з n елементів у математиці, відповідає запису в програмуванні. Кожна її компонент береться зі своєї окремої області, як і у разі запису. Єдина відмінність полягає в тому, що компонент визначається своїм розташуванням (позицією), а не ім'ям. Реляційна модель даних працює з безліччю впорядкованих наборів, які відповідають файлам записів, що зберігаються в машині. Також математична логіка використовується і в інших галузях інформатики – це у розробці в галузі моделювання та автоматизації інтелектуальних процедур – напрямок так званого штучного інтелекту.

Висновок

Математична логіка чимало сприяла бурхливому розвитку інформаційні технологіїу XX столітті, але з її поля зору випало поняття "судження", яке з'явилося у логіці ще за часів Аристотеля і на якому, як на фундаменті, тримається логічна основа природної мови. Таке недогляд аж ніяк не сприяло розвитку логічної культури суспільства і в багатьох навіть породило ілюзію, що комп'ютери здатні мислити не гірше за саму людину. Багатьох навіть не бентежить та обставина, що на тлі загальної комп'ютеризації напередодні третього тисячоліття логічні безглуздості в межах самої науки (я вже не говорю про політику, законотворчу діяльність і про псевдонауку) зустрічаються навіть частіше, ніж наприкінці XIX століття. І для того, щоб зрозуміти суть цих безглуздостей, немає необхідності звертатися до складних математичних структур з багатомісними відносинами та рекурсивними функціями, що застосовуються у математичній логіці. Виявляється, для розуміння та аналізу цих безглуздостей цілком достатньо застосувати набагато простішу математичну структуру судження, яка не тільки не суперечить математичним основамсучасної логіки, але в чомусь доповнює та розширює їх.

Список використаної літератури

1. Ігошин, В.І. Математична логіка та теорія алгоритмів [Текст]/В.І. Ігошин. – М.: Академія, 2008. – 448 с.; з іл.

Стяжкін, Н.І. Формування математичної логіки [Текст]/Н.І. Стяжкін. – М.: Наука, 1967. – 508 с.; з іл.

Марков, А.А. Елементи математичної логіки [Текст]/А.А. Марків. – М.: МДУ, 2004. – 310 с.; з іл.

Каррі, Х.Б. Підстави математичної логіки [Текст] / Х.Б. Каррі. - М: Мир, 1969. - 568 с.; з іл.

Репетиторство

Потрібна допомога з вивчення якоїсь теми?

Наші фахівці проконсультують або нададуть репетиторські послуги з цікавої для вас тематики.
Надішліть заявкуіз зазначенням теми прямо зараз, щоб дізнатися про можливість отримання консультації.

Буде присвячений основам математичної логіки, яка є не лише окремим розділом математики, а й має величезне значенняпри вивченні всієї вежі (та й не лише вишки). «Існує і єдино», «з цього випливає це», «необхідна умова», «достатність», «тоді й тільки тоді» – знайомі обороти, чи не так? І це не просто «чергові» штампи, якими можна знехтувати – це стійкі вираження, що володіють суворим змістом, з яким ми і познайомимося у цій статті. Крім того, матеріал буде корисний початківцям вивчати безпосередньо математичну логіку – я розгляну її базу: висловлювання та дії над ними, формули, основні закони + деякі практичні завдання. І, звичайно ж, ви дізнаєтеся дуже важливе, а подекуди й дуже кумедне відмінність матлогіки від нашої «звичайної» логіки. Починаємо закладати фундамент:

Висловлювання та висловлювальні форми

Висловлювання– це пропозиція, про яку можна сказати, істинновоно чи хибно. Висловлювання зазвичай позначають малими латинськими літерами, А їх істинність/хибність одиницею і нулем відповідно:

– цей запис (не плутати з модулем!) говорить нам про те, що висловлювання істинно;
– а цей запис – про те, що висловлювання хибно.

Наприклад:

– черепахи не літають;
- Місяць квадратний;
- Двічі два буде два;
– п'ять більше, ніж три.

Цілком зрозуміло, що висловлювання та істинні: ,
а висловлювання та – хибні:

Зрозуміло, далеко ще не всі пропозиції є висловлюваннями. До таких, зокрема ставляться питання та спонукальні пропозиції:

Ви не підкажете, як пройти в бібліотеку?
Ходімо в лазню!

Очевидно, що тут не йдеться про істину чи брехню. Як не йдеться про них мови і у разі невизначеності або неповної інформації:

Завтра Петя складе іспит- Навіть якщо він все вивчив, то не факт, що здасть; і навпаки - якщо нічого не знає, то може і здасть "на шару".

…так добре, Співати, не переживай – здаси =)

- А тут ми не знаємо, чому одно «ен», тому це теж не висловлювання.

Однак останню пропозицію можна визначити до висловлювання, а точніше, до висловної форми, вказавши додаткову інформацію про ен. Як правило, висловлювальні форми записуються з так званими кванторами. Їх два:

– квантор спільності (перегорнута букваA – від англ.All)розуміється і читається як "для всіх", "для будь-якого (ой) (их)";

– квантор існування (розгорнута букваE – від англ.Exist)розуміється і читається як «існує».

– для будь-кого натурального числавиконано нерівність. Ця висловлювальна форма хибнаоскільки їй, очевидно, не відповідають натуральні числа.

– а ось це висловлювальна форма вже істинна, як істинноі, наприклад, таке твердження:
…ну а що, хіба існує натуральне число, яке менше ніж –10?

Застерігаю вас від необачного використання даного квантора, бо «для будь-кого» може насправді виявитися зовсім і «не для будь-кого».

Увага! Якщо вам щось не зрозуміло в позначках, будь ласка, поверніться до уроку про множинах.

- Існує натуральне число, Яке більше двох. Істина…і, ​​головне, не посперечаєшся =)

– Брехня

Нерідко квантори «працюють в одній упряжці»:

– для будь-кого вектораІснує протилежний йому вектор. Величезна істина, а точніше, аксіома (Твердження, що приймається без доказу)векторний простір.

Зверніть увагу, що квантор існування має на увазі сам фактіснування об'єкта (хоча б одного), який задовольняє певним характеристикам. Нехай у світі існують єдина біла ворона, але ж існують. Більше того, в математиці (як шкільній, так і вищій) доводиться безліч теорем на існуванняі якраз єдиністьчогось. Доказ такої теореми складається із двох частин:

1) Існування об'єкта, що задовольняє певним критеріям. У цій частині обґрунтовується сам факт його існування.

2) Єдиність цього об'єкта. Цей пункт доводиться, як правило, методом від протилежного, тобто. передбачається, що існує 2-й об'єкт з такими ж характеристиками і далі це припущення спростовується.

Школярів, втім, намагаються не лякати подібною термінологією, і теорема часто подається в завуальованому вигляді, наприклад:

У будь-який трикутник можна вписати коло і, причому лише одну

До речі, а що таке загалом теорема? Логічну сутьцього страшного слова ми дізнаємося дуже скоро.

Логічні операції (дії над висловлюваннями)

Подібно до того, як з числами можна проводити арифметичні дії (складати, множити і т.д.), до висловлювань теж застосовні свої операції. Існує три базові логічні операції:

запереченнявисловлювання;

кон'юнкціячи логічне множення висловлювань;

диз'юнкціячи логічне складання висловлювань.

По порядку:

1) Заперечення висловлювання

НЕта символ

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

Так, наприклад, висловлювання – черепахи не літаютьістинно: ,
а його заперечення – черепахи літають якщо гарненько штовхнути- Помилково: ;

висловлювання - Двічі два буде двахибно: ,
а його заперечення - Невірно, що двічі дві буде два- Істинно: .

До речі, не треба сміятися з прикладу з черепахами;) садисти

Вдалою фізичною моделлю цієї операції є звичайна лампочка та вимикач:

світло увімкнено – логічна одиниця або істина,
світло вимкнули – логічний нуль чи брехня.

2) Кон'юнкція (логічне множення висловлювань)

Даної операції відповідає логічна зв'язка Іі символ або

Кон'юнкцією (читається «а і бе»), яке істинно в тому і лише тому випадку, коли істинні обидвависловлювання та:

Ця операція теж зустрічається часто-густо. Повернемося до нашого героя з першої парти: припустимо, що Петя отримує допуск до іспиту з вищої математикиякщо здає курсову роботу ізалік на тему. Розглянемо такі висловлювання:
– Петро здав курсову роботу;
– Петро здав залік.

Зауважте, що на відміну від формулювання «Петя завтра здасть»тут уже будь-якої миті часу можна сказати, істина це чи брехня.

Висловлювання (суть – Петра допущено до іспиту)буде істинно в тому і лише тому випадку, якщо він здав курсовик ізалік по . Якщо хоч щось не здано (Див. три нижніх рядки таблиці), то кон'юнкція – хибна.

І дуже вчасно спало мені на думку відмінний математичний приклад: знак системи з'єднує рівняння/нерівності, що входять до неї, якраз за правилом І. Так, наприклад, запис двох лінійних рівнянь у системумає на увазі те, що ми повинні знайти ТАКЕ коріння (якщо вони існують), які задовольняють і першому ідругого рівняння.

Розглянута логічна операція поширюється і більшу кількість висловлювань. Умовно кажучи, якщо в системі 5 рівнянь, то її коріння ( у разі їх існування)повинні задовольняти і 1-му і 2-му і 3-му і 4-му і 5-му рівняння цієї системи.

І на закінчення пункту знову звернемося до доморощеної електротехніки: кон'юнктивне правило добре моделює вимикач у кімнаті та рубильник на електричному щитку у під'їзді (послідовне підключення). Розглянемо висловлювання:

– вимикач у кімнаті включений;

– рубильник у під'їзді включений.

Напевно, всі вже зрозуміли, що кон'юнкція читається що природно:
– вимикач у кімнаті включений ірубильник у під'їзді увімкнено.

Очевидно, що і тоді, коли . У трьох інших випадках (Проаналізуйте, яких)ланцюг розімкнеться і світло згасне: .

Давайте приєднаємо ще один вислів:
– рубильник на підстанції увімкнено.

Аналогічно: кон'юнкція буде істинною тоді і тільки тоді, коли . Тут, до речі, вже буде 7 різних варіантіврозрив ланцюга.

3) Диз'юнкція (логічне додавання висловлювань)

Цій операції відповідає логічна зв'язка АБОта символ

диз'юнкцієювисловлювань і називають висловлювання (читається «а чи бе»), яке хибне в тому і тільки тому випадку, коли хибні обидва висловлювання і :

Припустимо, що в екзаменаційному квиткуз вищої математики 2 питання та студент складає іспит, якщо відповість хоча б на одинпитання. Розглянемо такі висловлювання:
– Петро відповів на 1-е запитання;
– Петро відповів на друге запитання.

Диз'юнктивний запис читається просто і зрозуміло: Петро відповів на 1-й або 2-е питанняі має на увазі три справжні результати (Див. таблицю). При цьому іспит Петро не здасть у єдиному випадку– якщо «запоре» обидва питання:

Слід зазначити, що союз «або» ми дуже часто розуміємо як «що виключає або», і, більше того, його часто так і треба розуміти! З тієї ж фрази про складання іспиту людина, швидше за все, зробить висновок, що Петя відповів лише на 1-й або 2-й питання. Однак аналізоване АБО – це не обивательське «або».

Операція логічного додаваннятакож застосовна для трьох та великої кількостівисловлювань. Деякі лояльні викладачі задають 10-15 питань і ставлять іспит, якщо студент хоч щось знає =) Іншими словами, логічне АБО приховує за собою зв'язку «хоча б на один»(і вона зовсім не означає, що СТРОГО на один!).

Ну і давайте відвернемося від побутової електрики: переважна більшість сайтів Інтернету розташовані на професійних серверах, які постачаються, як правило, двома блоками живлення. У електротехніці це називається паралельним підключенням, яке якраз і моделює правило АБО – сервер працює, якщо справний хоча б одинблок живлення. Обладнання, до речі, підтримує «гарячу» заміну, тобто. згорілий БП можна замінити, не вимикаючи сервер. Така ж історія з жорсткими дисками – вони дублюються у так званому RAID-масиві, і більше, сам Дата-центр, де знаходяться сервери, зазвичай запитується двома незалежними електролініями + дизель-генератор про всяк випадок. Ці заходи дають змогу забезпечити максимальний аптайм сайтів.

І якщо мова зайшла про комп'ютери, то вони базуються на розглянутих логічних операціях! Це здається неймовірним, але замислимося - а що взагалі можуть "розуміти" ці "залізниці"? А розуміти вони можуть таке:

у дроті є струм – це логічна одиниця;
провід знеструмлений - це логічний нуль.

Саме цей факт є причиною того, що в основі вимірювання обсягу інформації лежить ступінь двійки:
і т.д.

Найпростішим «комп'ютером» є… звичайний вимикач – він зберігає інформацію в 1 біт (істину чи брехню у вказаному вище значенні). Центральний процесор сучасного комп'ютера налічує сотні мільйонів (!)транзисторів, і найскладніше програмне забезпечення, "Наворочена гра" розкладається на безліч нулів і одиниць, які обробляються за допомогою елементарних логічних операцій!

І вже наступні дві операції, які ми розглянемо, є не самостійними, тобто можуть бути виражені через заперечення, кон'юнкцію та диз'юнкцію:

Імплікація та логічне слідство.
Необхідна умова. Достатня умова

До болю знайомі обороти: "отже", "з цього випливає це", "якщо, то" і т.п.

Імплікацієювисловлювань (посилання)і (наслідок)називають висловлювання, яке хибно в єдиному випадку - коли істинно, а - хибно:

Фундаментальний сенс операції такий (читаємо та переглядаємо таблицю зверху вниз):

з істини може випливати тільки істинаі не може слідувати брехня;

з брехні може випливати все, що завгодно (Дві нижні рядки), при цьому:

істинність посилки є достатньою умовоюдля істинності укладання ,

а істинність укладання – є необхідною умовою для істинності посилки.

Розбираємось на конкретному прикладі:

Складемо імплікацію висловлювань – йде дощі – на вулиці сиро:

Якщо обидва висловлювання істинні, то само собою істинна і імплікація – якщо на вулиці йде дощ, то на вулиці сиро. При цьому не може бути такого, щоб йшов дощ, а на вулиці було сухо :

Якщо ж дощу немає, то на вулиці може бути як сухо :

так і сиро :
(наприклад, через те, що розтанув сніг).

А тепер ВДУМУЄМОСЯ у ці «штамповані» слова необхідністьі достатність:

Дощ є достатнімумовою для того, щоб на вулиці було сиро, і з іншого боку, вогкість на вулиці необхіднадля припущення про те, що пройшов дощ (Бо якщо сухо – то дощу точно не було).

Зворотна ж імплікація нелегальна: - вогкості на вулиці ще малодля обґрунтування факту дощу, і, крім того, дощ не є НЕОБХІДНОЮ причиною вогкості (т.к., наприклад, може пройти та розтанути град).

Начебто має бути зрозуміло, але про всяк випадок ще кілька прикладів:

– Щоб навчитися виконувати дії з матрицями, необхідновміти складати та множити числа. Але цього, як ви правильно передчуєте, мало.

– Щоб навчитися виконувати арифметичні дії достатньозакінчити 9 класів. Але це не є умовою необхідним- Вважати може навчити і бабуся, причому ще в дитячому садку.

– Щоб знайти площу трикутника достатньознати його бік та висоту, проведену до цієї сторони. Однак знову ж таки – це не необхідність, площу трикутника можна знайти і по трьох сторонах (формулі Герона) або, наприклад, за допомогою векторного твору.

– Для допуску до іспиту з вищої математики Пете необхіднозвітувати з курсової роботи. Але цього мало- Бо ще потрібно здати залік.

– Для того, щоб вся група отримала залік достатньозанести викладачеві ящик коньяку. І тут, як неважко припустити, відпадає необхідністьщось вчити =) Але, зверніть увагу, підготовка зовсім не забороняється;)

Чи бувають умови, необхідні і в той же час достатні? Звісно! І дуже скоро ми до них дістанемося. А зараз про один важливий принцип матлогіки:

Математична логіка формальна

Її цікавить істинність чи хибність висловлювань, але з їх зміст! Так, якщо ми складемо імплікацію Якщо черепахи не літають, то двічі дві одно чотирьом, то вона буде справжньою! Іншими словами, будь-яке справжнє висловлювання можна обґрунтувати будь-якою істиною (1-ий рядок таблиці), І з погляду формальної логіки це буде істина!

Але ще цікавіша ситуація з хибним посилом: будь-якою брехнею можна обґрунтувати все, що завгодно – як істину так і брехню:

- Якщо Місяць квадратний, то ;
– якщо пінгвіни ходять у валянках, то черепахи носять шльопанці.

А що? - За таблицею обидва висловлювання істинні!

Ці факти отримали назву парадокс імплікації, але насправді ми, звичайно, розглядаємо приклади, осмислені з погляду нашої змістовної логіки.

І ще один дуже важливий момент : імплікацію часто позначають значком (теж читається «отже», «з цього випливає це»), який ми також використовуємо під час вирішення завдань, доказів теорем і т.д. І тут мова йде про збіг позначень- Те, що ми використовуємо в «звичайних» математичних викладках, строго кажучи, не є імплікацією. В чому різниця? Коли ми вирішуємо завдання та пишемо, що («З а слідує бе»), то вважаємо висловлювання свідомо істинним, і більше, виводимо з нього іншу істину. У математичній логіці це називається логічним наслідком. Зазвичай слідство підлягає обґрунтуванню, і тому під час оформлення робіт завжди намагайтеся пояснювати, які аксіоми, теореми, вирішені завдання тощо. ви використовували для того чи іншого висновку.

Теорема за своєю суттю теж є логічним наслідком: її умова спирається на справжніпосилки (аксіоми, раніше доведені теореми тощо). Доказ встановлює істинність слідства , причому у процесі неможливо знайти використовувати помилкові міркування.

Недоведена теорема називається гіпотезою, і варіанти тут два: або вона виводить з істини істину і є теоремою, або гіпотеза неправильна, тобто. з безлічі справжніх посилок слід «не бе»: . У разі спростування виходить тривіальний висновок на кшталт « гіпотеза Івана Петрова невірна», Але і це, буває, дорогого коштує – дерзайте, шановні читачі!

Розглянемо як приклад, звичайно, не мегатеорему, але твердження, яке вимагає нехай простого, але обґрунтування. Хоча і його не буде =) =):

- Число ділиться на 4;
- Число ділиться на 2.

Очевидно, що слідство істинно, Тобто з того, що число ділиться на 4, випливає і його поділення на 2. І, відповідно, протилежний висновок - є брехня:

При цьому ще раз звертаю увагу на те, що посилка спочатку постулюється як істина. (На відміну від імплікації, де вона може бути і хибною).

Для логічних наслідків також у ході поняття необхідностіі достатності, Скопіюю пару рядків зверху:

істинність посилки – це достатня умовадля істинності укладання ,

істинність ув'язнення – це необхідна умовадля істинності посилки.

У нашому випадку:

Подільність числа на 4 є достатнімумовою у тому, щоб воно ділилося на 2. І з іншого боку, ділимість числа на 2 є необхіднимумовою ділимості на 4.

Слід зазначити, що розглянутий приклад можна записати і як імплікації:
(користуючись таблицею, проаналізуйте всі розклади самостійно)

Однак у загальному випадку «перенесення понять» некоректне! Тобто, якщо ми ведемо розмову про те, що , це ще не означає, що буде справедлива імплікація . І такий приклад я наведу у заключному пункті. і необхідно скласти 3 іспити (або сесія буде не здана)і в той же час цього достатньо (т.к. більше нічого робити не потрібно).

Особливість еквіваленції полягає в тому, що має місце або і те і інше, або нічого, наприклад:

Петя займається штангою тоді і лише тоді, коли Маша танцює на столі

Це означає, що або Петя займається штангою і Маша танцює на столі, або вони обоє лежать на дивані Петро, ​​ти заслужив! =) Такі ось дружні Петя та Маша. Тепер начебто схожа фраза без «тоді й тільки тоді»:

Петя займається штангою, коли Маша танцює на столі

Але сенс дещо змінився: тут можна припустити, що Петя, буває, тягає штангу і без Маші, і з іншого боку, Маші «до лампочки», чи гойдається під час її танцю Петя.

Ось у чому сила необхідної та достатньої умови! – воно об'єднує та дисциплінує =)

…хотів я для приколу розподілити ролі навпаки, але потім передумав… все ж таки не можна таке пропагувати =)

До речі, про дисципліну – раціональний підхід таки передбачає необхідність і достатність – коли людина задля досягнення будь-якої мети робить рівно стільки, скільки потрібно, і не більше. Це, звичайно, буває нудно у звичайному житті, але всіляко вітається в математичних міркуваннях, які нас вже зачекалися:

Трикутник є рівностороннім тоді і лише тоді, коли в нього рівні кути

Висловлювання – трикутник рівностороннійі – у нього рівні кутиможна співвіднести еквіваленцією, але на практиці ми майже завжди пов'язуємо їх гострою обозначністю логічного слідства називається гіпотенузою

Цей пункт- Це власне і є теорема Піфагора, формулювання якої нам знайоме ще зі школи: "Якщо трикутник прямокутний, то".

2) На другому кроці обґрунтовується достатність:
– тут треба довести, що справедливість рівності достатнядля того, щоб трикутник був прямокутним.

Учнів знову ж таки такими словами не залякують, і другий пункт формулюють у вигляді зворотної теоремиПіфагора: "Якщо , то трикутник прямокутний".

Зв'язків за схемою «тоді й тільки тоді» в математиці дуже багато, і я щойно навів стандартну схему їхнього доказу. І, звичайно, завжди аналізуйте, що означають «необхідно»

Чекаю на вас у другій частині нашого захоплюючого уроку, де ми познайомимося з основними логічними формулами та законами, а також вирішуємо практичні завдання. Для вирішення завдань потрібно п'ять табличок з цієї сторінки, тому я рекомендую відразу переписати їх на листок – щоб вони були перед очима.

Крім того, я відкрию вам секрет успішного вивчення математичної логіки;)

Основна ідея математичної логіки – формалізація знань та міркувань. Відомо, що знання, що найбільш легко формалізуються, - математичні. Таким чином, математична логіка по суті - наука про математику, або метаматематика. Центральним поняттям математичної логіки є "математичний доказ"". Справді, "доказові"" (інакше кажучи, дедуктивні) міркування - єдиний видвизнаних у математиці міркувань. Міркування у математичній логіці вивчаються з погляду форми, а чи не сенсу. По-суті, міркування моделюються суто "механічним" процесом переписування тексту (формул). Такий процес називають висновком. Кажуть ще, що математична логіка оперує лише синтаксичними поняттями. Однак зазвичай все ж таки важливо, як співвідносяться міркування з дійсністю (або нашими уявленнями). Тому, треба все ж таки мати на увазі деякий зміст формул і висновку. При цьому використовують термін семантика (синоном слова "смисл") і чітко поділяють синтаксис та семантику. Коли ж дійсно цікавляться тільки синтаксисом, часто використовують термін "формальна система". Ми будемо використовувати синонім цього терміну - "обчислення"" (використовуються ще терміни "формальна теорія"" і "аксіоматика""). Об'єктом формальних систем є рядки тексту (послідовності символів), з допомогою яких записуються формули.

Формальну систему визначено, якщо:

Задано алфавіт (безліч символів, що використовуються для побудови формул).

Виділено безліч формул, які називаються аксіомами. Це – стартові точки у висновках.

Задано безліч правил виведення, які дозволяють із деякої формули (або безлічі формул) отримувати нову формулу.

Основні засади операцій

Заперечення

Заперечення логічного висловлювання - логічне висловлювання, що набуває значення "істинно", якщо вихідне висловлювання хибне, і навпаки. Це спеціальна логічна операція. Залежно від розташування розрізняють зовнішнє і внутрішнє заперечення, властивості та ролі яких істотно різняться.

1. Зовнішнє заперечення (пропозиціональне) служить утворенню складного висловлювання з іншого (не обов'язково простого) висловлювання. У ньому стверджується відсутність стану справ, що описується у заперечуваному висловлюванні. Традиційно негативне висловлюваннявважається істинним, якщо, і тільки якщо, заперечення висловлювання хибне. У природною мовоюзаперечення зазвичай виражається оборотом «невірно, що», за яким слідує заперечення висловлювання.

У мовах формальних теорій заперечення називається особлива унарна пропозиційна зв'язка, що використовується для освіти з однієї формули іншої, складнішої. Для позначень заперечення зазвичай використовуються символи "заперечення", "-" або "--1". У класичній логіці висловлювань формула А істинна тоді і тільки тоді, коли формула А помилкова.

Однак у некласичній логіці заперечення може не мати всі властивості класичного заперечення. У зв'язку з цим виникає цілком закономірне питання про мінімальному наборівластивостей, якому повинна задовольняти деяка унарна операція, щоб її можна було вважати запереченням, а також про принципи класифікації різних запереченнях у некласичних формальних теоріях (див.: Dunn JM і Hardegree GM Algebraic Methods in Philosophical Logic. Oxford, 200).

Фактично вказане вище традиційне розуміннязовнішнього (пропозиційного) заперечення може бути виражено через систему наступних вимог: (I) Якщо А - істинно (хибно), то не-А - хибно (істинно); (II) Якщо не-А - істинно (хибно), то А - хибно (істинно). Формально вимоги (I) і (II) можуть бути виражені через умову (1) А р--iB=>B (= --, А, зване «конструктивна контрапозиція»). Проте виявляється, що умову (1) можна розкласти на два більше слабких умов: (2) А (= В=>-,В р-Аі(3)А(= -- 1 -- А, відомих, відповідно, як «контрапозиція» та «введення подвійного заперечення». В результаті з'являється можливість виявити підмінімальне Заперечення, що задовольняє умові (2), але не задовольняє умові (3). .задовольняє умові (1) або умовам (2) і (3) разом), для якого виконується умова (4), називається заперечення де Моргана. додаткової якості(5): Якщо А - * В, то для будь-якого С вірно, що А р С («властивість абсурдності»), - називається інтуїціоністським запереченням. Можна сформулювати принцип (6), двоїстий принципу абсурдності: Якщо В |=Аі-S р А, то для будь-якого С вірно, що С р А. Задовольняє цьому принципу заперечення. є різновидом заперечення в паранесуперечливій логіці. Нарешті, заперечення де Моргана (властивості (2), (3), (4)), для якого виконується (5) або (6), називається орто-заперечення Якщо у відповідному обчисленні приймається аксіома дистрибутивності для кон'юнкції та диз'юнкції, то орто- заперечення називається заперечення Буля, чи класичним запереченням.

2. Внутрішнє заперечення входить до складу простого висловлювання. Розрізняють заперечення у складі зв'язки (негативна зв'язка) та термінове заперечення.

Заперечення у складі зв'язки виражається за допомогою частки «не», що стоїть перед дієсловом-зв'язкою (якщо він є) або перед смисловим дієсловом. Воно служить висловлювання суджень про відсутність якихось відносин («Іван знає Петра»), чи освіти негативної предицирующей зв'язки у складі категоричних атрибутивних суджень.

Термінове заперечення використовується для утворення негативних термінів. Воно виражається через приставку «не» чи близькі їй за змістом («Всі незрілі яблука – зелені»).

Кон'юнкція

Кон'юнкція двох логічних висловлювань - логічне висловлювання, істинне лише тоді, коли вони одночасно істинні (від латів. conjunctio - союз, зв'язок), широкому значенні- Складне висловлювання, утворене за допомогою союзу «і». У принципі можна говорити про кон'юнкцію нескінченного числависловлювань (наприклад, про кон'юнкцію всіх справжніх речень математики). У логіці кон'юнкцією називають логічну зв'язку (операцію, функцію; позначають: &,); освічене з її допомогою складне висловлювання істинно лише за умови однакової істинності його складових. У класичній логіці висловлювань кон'юнкція разом із запереченням складають функціонально-повну систему пропозиційних зв'язок. Це означає, що через них можна визначити будь-яку іншу зв'язку. Однією з властивостей кон'юнкції є комутативність (тобто еквівалентність А&В та В&А). Однак, іноді, говорять про некомутативну, тобто впорядковану кон'юнкцію (прикладом висловлювання з такої кон'юнкції може служити: «Смітник свиснув, і коні поскакали»).

Диз'юнкція

Диз'юнкція двох логічних висловлювань - логічне висловлювання, істинне лише тоді, коли хоча б одне з них істинно

(від латів. disjunctio - роз'єднання, відокремлення), у сенсі - складне висловлювання, утворене з двох чи більше пропозицій з допомогою союзу «або», виражає альтернативність, чи вибір.

У символічній логіці диз'юнкцією називають логічну зв'язку (операцію, функцію), що утворює з пропозицій А і складне висловлювання, що позначається зазвичай як А V В, яке є істинним при істинності принаймні одного з двох диз'юнктивних членів: Аабо в.

У класичній логіці диз'юнкція разом із запереченням утворює функціонально-повну систему пропозиціональних зв'язок, що дозволяє визначити через них інші пропозиціональні зв'язки.

Традиційно прийнято відрізняти розглянуту (нестрогу) диз'юнкцію від суворої (розділювальної) диз'юнкції, для якої характерно те, що відповідне висловлювання є істинним за умови, коли дійсний один і тільки один диз'юнктивний член.

Імплікація

Імплікація двох логічних висловлювань A і B - логічне висловлювання, хибне тільки тоді, коли B хибно, а A істинно (від лат. implicatio - сплетення, від implico - тісно пов'язую) - логічна зв'язка, що відповідає граматичній конструкції «якщо. ., то...», за допомогою якої з двох простих висловлюваньутворюється складне висловлювання. В імплікативному висловлюванні розрізняють антецедент (підстава) - висловлювання, що йде після слова "якщо", і консеквент (наслідок) - висловлювання, що йде за словом "то". Імплікативний вислів представляє в мові логіки умовне висловлювання звичайної мови. Останнє грає особливу роль, як у повсякденних, і у наукових міркуваннях, основний його функцією є обгрунтування одного шляхом посилання щось інше.

Висловлювану умовним висловлюванням зв'язок обосновывающего і обгрунтовуваного важко охарактеризувати у вигляді, і іноді природа її щодо зрозуміла. Цей зв'язок може бути, зокрема, зв'язком логічного слідування, що має місце між посилками та укладанням правильного висновку («Якщо всі живі багатоклітинні істоти смертні і медуза є такою істотою, то вона смертна»). Зв'язок може являти собою закон природи («Якщо тіло піддати тертю, воно почне нагріватися») або причинний зв'язок(«Якщо Місяць у молодик знаходиться у вузлі своєї орбіти, настає сонячне затемнення»). Розглядається може мати також характер соціальної закономірності, правила, традиції тощо. («Якщо змінюється економіка, змінюється і політика», «Якщо обіцянка дана, вона має бути виконана»).

Зв'язок, що виражається умовним висловом, передбачає, що консеквент з певною необхідністю «випливає» з антецедента і є певний загальний закон, зумівши сформулювати який ми можемо логічно вивести консеквент з антецедента. Наприклад, умовний вислів «Якщо вісмут - метал, він пластичний» передбачає загальний закон «Всі метали пластичні», що робить консеквент цього висловлювання логічним наслідком його антецедента.

І в звичайній мові, і в мові науки умовне висловлювання, крім функції обґрунтування, може виконувати також низку інших завдань. Воно може формулювати умову, яка не пов'язана з к.-л. загальним законом або правилом («Якщо захочу, розріжу свій плащ»), фіксувати якусь послідовність («Якщо минуле літо було сухим, то цього року воно дощове»), виражати в своєрідній формі зневіру («Якщо ви вирішите завдання, я доведу велику теоремуФерма»), протиставлення («Якщо у городі росте капуста, то саду росте яблуня») тощо. Численність та різнорідність функцій умовного висловлювання істотно ускладнює його аналіз.

У логічних системах абстрагуються від особливостей простого вживання умовного висловлювання, що веде до різних імплікацій. Найбільш відомі з них імплікація матеріальна, сувора імплікація та релевантна (доречна) імплікація.

Матеріальна імплікація - одне з основних зв'язок класичної логіки. Визначається вона в такий спосіб: імплікація хибна лише у разі істинності антецедента і хибності консеквента і істинна в інших випадках. Умовне висловлювання «Якщо А, то В» передбачає деякий реальний зв'язок між тим, про що йдеться в А та В; вираз «А матеріально імплікує» такого зв'язку не передбачає.

Сувора імплікація визначається через модальне поняття (логічної) неможливості: «А суворо імплікує» означає «Неможливо, щоб А було істинно, а помилково».

У релевантній логіці імплікація сприймається як умовний союз у його звичному значенні. У разі релевантної імплікації не можна сказати, що справжнє висловлювання може бути обґрунтоване шляхом посилання на будь-яке висловлювання і що за допомогою хибного висловлювання можна обґрунтувати будь-яке висловлювання.

Еквівалентність

Еквівалентність двох логічних висловлювань - логічне висловлювання, істинне лише тоді, що вони одночасно істинні чи хибні (від позднелат. equivalens - рівноцінний) - родове найменування різноманітних відносин типу рівності, тобто. рефлексивних, симетричних та транзитивних бінарних відносин. Приклади: еквіполентність (збіг за змістом, значенням, змістом, виразними та (або) дедуктивними можливостями між поняттями, концепціями, наук. теоріями або формальними їх формальними системами) конгруентність або подоба геометрія, фігур; ізоморфізм; рівносильність множин та інші еквівалентність будь-яких об'єктів означає їх рівність (тотожність) у будь-якому відношенні

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

Розгляд класів еквівалентності як нових об'єктів є одним із основних способів породження (введення) абстрактних понять у логіко-математичних (і взагалі природничо-наукових) теоріях. Так, вважаючи еквівалентними дроби a/b та c/d з цілими чисельниками та знаменниками, якщо ad=bc, вводять у розгляд раціональні числа як класи еквівалентних дробів; вважаючи еквівалентними множини, між якими можна встановити взаємно-однозначну відповідність, вводять поняття потужності (кардинального числа) множини (як клас еквівалентних між собою множин); вважаючи еквівалентними два шматки речовини, що вступають у рівних умовах в однакові хімічні реакції, приходять до абстрактного поняття хімічного складуі т.п.

Термін "еквівалентність" вживають часто не (тільки) як родовий, а як синонім деяких з його приватних значень ("еквівалентність теорій" замість "еквівалентність", "еквівалентність множин" замість "рівнопотужність", "еквівалентність слів" в абстрактній алгебрі " і т.п.).

Кванторний вислів

Кванторне з квантором загальності.

Кванторне логічне висловлювання з квантором загальності ( " xA ( x ) ) -- логічне висловлювання , істинне лише тоді , коли кожного об'єкта x із заданої сукупності висловлювання A ( x ) істинно .

Кванторне із квантором існування.

Кванторне логічне висловлювання з квантором існування ($xA(x)) -- логічне висловлювання, істинне лише тоді, як у заданої сукупності існує об'єкт x, такий, що висловлювання A(x) істинно.

Структура математичної логіки

Розділ «математична логіка» складається з трьох частин: за неформальним аксіоматичний метод, за логікою висловлювань і за логікою предикатів (першого порядку). Аксіоматичний метод побудови – перший крок на шляху до формалізації теорії. Більшість завдань, що розглядаються в математичній логіці, полягає у доказі деяких тверджень. Математична логіка має багато розгалужень. Вона застосовує таблична побудовалогіки висловлювань, використовує спеціальну мову символів та формули логіки висловлювань.

Неформальний аксіоматичний метод

Аксіоматичний метод, який не фіксує жорстко застосовуваної мови і тим самим не фіксує межі змістовного розуміння предмета, але вимагає аксіоматичного визначення всіх спеціальних для даного предмета дослідження понять. Цей термін немає загальноприйнятого тлумачення.

Історія розвитку аксіоматичного методу характеризується все більшим ступенем формалізації. Неформальний аксіоматичний метод – певний ступінь у цьому процесі.

Початкова, дана Евклідом, аксіоматична побудова геометрії відрізнялася дедуктивним характером викладу, при якому в основу клалися визначення (пояснення) та аксіоми (очевидні твердження). З них, спираючись на здоровий глузд і очевидність, виводилися слідства. При цьому у висновку неявно іноді використовувалися не зафіксовані в аксіомах припущення геометрія, характеру, що особливо відносяться до руху в просторі взаємному розташуваннюпрямих та точок. Згодом було виявлено геометрію, поняття та їх вживання аксіоми, що неявно використовуються Евклідом та його послідовниками. При цьому виникало питання: чи справді виявлено усі аксіоми. Керівний принцип для вирішення цього питання сформулював Д. Гільберт (D. Hilbert): "Слід домогтися того, щоб з рівним успіхом можна було говорити замість точок, прямих і площин про столи, стільці та пивні кухлі". Якщо доказ не втрачає доказової сили після такої заміни, то всі спеціальні припущення, що використовуються в цьому доказі, зафіксовані в аксіомах. Ступінь формалізації, що досягається при такому підході, являє собою рівень формалізації, характерний для неформального аксіоматичного методу. Еталоном тут може бути класична праця Д. Гільберта "Підстави геометрії".

Неформальний аксіоматичний метод застосовується як надання певної завершеності аксіоматично викладеної конкретної теорії. Він є дієвою зброєю математичного дослідження. Оскільки щодо системи об'єктів з цього методу немає їх специфіка, чи " природа " , то доведені твердження переносяться будь-яку систему об'єктів, задовольняє аналізованим аксіомам. Відповідно до неформального аксіоматичного методу, аксіоми - це неявні визначення початкових понять (а чи не очевидні істини). Що являють собою об'єкти, що вивчаються - неважливо. Все, що потрібно про них знати, сформульовано в аксіомах. Предметом вивчення аксіоматичної теорії є будь-яка її інтерпретація.

Неформальний аксіоматичний метод, окрім неодмінного аксіоматичного визначення всіх спеціальних понять, має й іншу характерну особливість. Це вільне, неконтрольоване аксіомами, засноване на змістовному розумінні використання ідей та понять, які можна застосувати до будь-якої мислимої інтерпретації, незалежно від її змісту. Зокрема, широко використовуються теоретико-множинні і логічного поняття та принципи, а також поняття, пов'язані з ідеєю рахунку, та ін. на якому формулюються та доводяться властивості аксіоматично заданої системи об'єктів. Фіксування мови веде до поняття формальної аксіоматичної системи та створює матеріальну основу для виявлення та чіткого опису допустимих логічних принципів, для контрольованого вживання теоретико-множинних та інших загальних чи не спеціальних для досліджуваної галузі понять. Якщо в мові немає засобів (слів) для передачі теоретико-множинних понять, то цим відсіваються всі докази, що ґрунтуються на використанні таких засобів. Якщо в мові є засоби для вираження деяких теоретико-множинних понять, їх застосування в доказах можна обмежити певними правилами або аксіомами.

Фіксуючи по-різному мову, отримують різні теоріїосновний об'єкт розгляду. Наприклад, розглядаючи мову вузького обчислення предикатів для теорії груп, одержують елементарну теоріюгруп, у якій не можна сформулювати будь-якого твердження про підгрупи. Якщо перейти до мови обчислення предикатів другого ступеня, з'являється можливість розглядати властивості, у яких фігурує поняття підгрупи. Формалізацією неформального аксіоматичного методу в теорії груп служить перехід до мови системи Цермело - Френкеля з її аксіоматикою.

Аксіоматичний метод

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

Ідея аксіоматичного методу вперше була висловлена ​​у зв'язку з побудовою геометрії в Стародавній Греції (Піфагор, Платон, Аристотель, Евклід). Для сучасної стадіїрозвитку аксіоматичного методу характерна висунута Гільбертом концепція формального аксіоматичного методу, яка ставить завдання точного описулогічних засобів виведення теорем із аксіом. Основна ідея Гільберта - повна формалізація мови науки, при якій її судження розглядаються як послідовності знаків (формули), що набувають сенсу лише за деякої конкретної інтерпретації. Для виведення теорем із аксіом(і взагалі одних формул з інших) формулюються спец. правила виведення. p align="justify"> Доказ у такій теорії (обчисленні, або формальної системі) - це деяка послідовність формул, кожна з яких або є аксіома, або виходить з попередніх формул послідовності за яким-небудь правилом виведення. На відміну від таких формальних доказів, властивості самої формальної системи загалом вивчаються. засобами метатеорії. Основні вимоги до аксіоматичних формальних систем - несуперечність, повнота, незалежність аксіом. Гільбертівська програма, яка передбачала можливість довести несуперечність і повноту всієї класичної математики, загалом виявилася нездійсненною. У 1931 Гедел довів неможливість повної аксіоматизації досить розвинених наукових теорій(Напр., Арифметики натуральних чисел), що свідчило про обмеженість аксіоматичного методу. Основні принципи аксіоматичних методів були піддані критиці прихильниками інтуїціонізму та конструктивного спрямування.

Вступ

Тема контрольної роботи"Математична логіка".

Буль або Бул, а також Буул, Джордж (1815-1864) - англійський математик, який вважається основоположником математичної логіки.

Математична логіка – це розділ математики, присвячений аналізу методів міркувань, у своїй насамперед досліджуються форми міркувань, а чи не їх зміст, тобто. досліджується формалізація міркувань.

Формалізація міркувань перегукується з Аристотелю. Сучасний виглядаристотелева (формальна) логіка набула у другій половині ХІХ століття у творі Джорджа Буля “Закони думки”.

Інтенсивно математична логіка почала розвиватися в 50-х роках XX століття у зв'язку з бурхливим розвитком цифрової техніки.

1. Елементи математичної логіки

Основними розділами математичної логіки є обчислення висловлювань та обчислення предикатів.

Висловлювання – є пропозиція, яка може бути або істинною, або хибною.

Обчислення висловлювань – вступний розділ математичної логіки, у якому розглядаються логічні операції з висловлюваннями.

Предикат - логічна функція від п змінних, яка набуває значення істинності чи хибності.

Обчислення предикатів - розділ математичної логіки, об'єктом якого є подальше вивчення та узагальнення обчислення висловлювань.

Теорія булевих алгебр (булевих функцій) покладено основою точних методів аналізу та синтезу теорії перемикачів при проектуванні комп'ютерних систем.

1.1 Основні поняття алгебри логіки

Алгебра логіки – розділ математичної логіки, вивчає логічні операції над висловлюваннями.

У алгебрі логіки цікавляться лише істинним значенням висловлювань. Істиннісні значення прийнято позначати:

1 (істина) 0 (брехня).

Кожній логічній операції відповідає функція, яка набирає значення 1 або 0, аргументи якої також приймають значення 1 або 0.

Такі функції називаються логічними або булевими, або функціями логіки алгебри (ФАЛ). При цьому логічна (булева) змінна xможе приймати лише два значення:

Таким чином,

У цьому випадку алгебру логіки можна визначити, як сукупність множини логічних функційіз заданими у ньому всілякими логічними операціями. Таким логічним операціямяк кон'юнкція (читається І), диз'юнкція ( АБО), імплікація, еквівалентність, заперечення ( НЕ), відповідають логічні функції, для яких прийнято позначення

Це табличний спосіб завдання ФАЛ. Поряд із ними застосовується завдання функцій за допомогою формул у мові, що містить змінні x , y , …, z(можливо індексовані) та символи деяких конкретних функцій – аналітичний спосіб завдання ФАЛ.

Найбільш уживаною є мова, що містить логічні символи

1) усі змінні є формули;

2) якщо Pі Q- Формули, то

Наприклад, вираз

Кажуть що Формула реалізує функцію.Так формула

Нехай Pі Q- Формули, які реалізують функції f (x 1 , x 2 , …, x n) та g (x 1 , x 2 , …, x n). Формули рівні: P = Q, якщо функції fі gзбігаються, тобто. збігаються їх таблиці істинності. Алгебра, основним безліччю якої є безліч логічних функцій, а операціями – диз'юнкція, кон'юнкція і заперечення, називається булевою алгеброю логічних функцій.

Наведемо закони та тотожності, що визначають операції

1. Ідемопотентність кон'юнкції та диз'юнкції:

2. Комутативність кон'юнкції та диз'юнкції:

3. Асоціативність кон'юнкції та диз'юнкції:

4. Дистрибутивність кон'юнкції щодо диз'юнкції та диз'юнкції щодо кон'юнкції:

5. Подвійне заперечення:

6. Закони де Моргана:

7. Склеювання:

8. Поглинання

9. Дії з константами 0 та 1.