Логика

Основные логические символы

Логика в программировании

Серьёзнейшей проблемой для информатики и компьютерных наук является наличие ошибок в алгоритмах и программах, публикуемых в учебниках и учебных пособиях, а также неумение преподавателями и учителями информатики выявлять и исправлять ошибки в алгоритмах и программах, составляемых учащимися.

Тестирование программ может выявить наличие ошибок в программах, но не может гарантировать их отсутствие. Гарантии отсутствия ошибок в алгоритмах и программах могут дать только доказательства их правильности. Алгоритм не содержит ошибок, если он дает правильные решения для всех допустимых данных.

Единственный путь для преодоления этих проблем является изучение систематическим методам составления алгоритмов и программ с одновременным анализом их правильности в рамках доказательного программирования с самого начала обучения основам алгоритмизации и программирования.

Сложность для преподавателей информатики и профессиональных программистов заключается в том, что они должны уметь писать не только алгоритмы и программы без ошибок, но и при этом писать доказательства правильности своих алгоритмов и программ. Что сейчас не умеют делать ни математики, ни программисты, ни преподаватели информатики.

В результате «профессиональные» программисты пишут программы с большим числом ошибок, которые они не могут ни выявить, ни исправить. Массированное тестирование программ на ЭВМ приносит программистам несомненную пользу, однако не дает гарантий полного избавления от ошибок.

Практика применения и доказательных методов программирования показала, что эта технология вполне доступна студентам математических факультетов, которым вполне по силам написание доказательств правильности алгоритмов, после проверки и тестирования программ на ЭВМ.

Наибольший эффект в освоении технологий доказательного программирования наблюдается на экзаманех по информатике в математических и экономических вузах, где студенты справляются и с решением задач на ЭВМ и написанием доказательств правильности алгоритмов и программ.

Интуитивные методы анализа правильности алгоритмов и программ характерны для олимпиад по информатике и программированию, где победителями и призёрами становятся те студенты, которые освоили технику тестирования программ на ЭВМ и составления алгоритмов и программ без ошибок.

Типы и функции знаков препинания

В современной латинской, кириллической, арабской, еврейской, индийской письменности выделяются знаки препинания, выполняющие следующие функции:

• выделение законченных смысловых отрезков текста — предложений — с одновременным указанием на их коммуникативный тип, эмоциональную окраску, степень законченности (точка, вопросительный и восклицательный знаки, многоточие);
• указание на отношения между частями предложения (запятая, точка с запятой, двоеточие, тире);
• выделение прямой речи, цитат (кавычки);
• указание на эмоциональное отношение к отдельным словам и словосочетаниям (кавычки, вопросительный и восклицательный знаки, заключённые в скобки);
• указание на пропуски текста (многоточие);
• знаки сокращений слов (точка, дефис, косая черта и другие).

Знаки препинания бывают одиночными и парными. К парным знакам препинания относятся две запятые и два тире (употребляемые при обособлении частей предложения как единые знаки), скобки и кавычки.

В качестве особого знака препинания выделяется красная строка, служащая для разделения крупных смысловых отрезков текста, перехода к новой «теме» повествования, а также пробел, отделяющий слова друг от друга.

Примечания

1. ↑ , с. 264—266, 534—536.
2. . // Website Online Etymology Dictionary. Дата обращения 7 февраля 2016.
3. , с. 67.
4. Стяжкин Н. И. . Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 321, 348, 352, 368.
5. . // Website Jeff Miller Web Pages. Дата обращения 7 февраля 2016.
6. , с. 30.
7. Пратт Т. . Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.
8. Грогоно П. . Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.
9. Вегнер П. . Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.
10. , Строуструп Б. . Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.
11. Яблонский С. В. . Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.
12. Рвачёв В. Л. . Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.
13. ↑ Словарь по кибернетике. 2-е изд / Под ред. В. С. Михалевича. — Киев: Украинская советская энциклопедия, 1989. — 751 с. — ISBN 5-88500-008-5.

Обозначения

Наиболее часто встречаются следующие обозначения для операции конъюнкции:

a∧b,a&&b,a&b,a⋅b,aANDb,min(a,b){\displaystyle a\land b,\quad a\And \And b,\quad a\And b,\quad a\cdot b,\quad a\,\,\mathrm {AND} \,\,b,\quad \min(a,b)}

(в случае использования точки, как знака логического умножения, этот знак, как и при обычном умножении в алгебре, может быть опущен: ab{\displaystyle ab}).

При этом обозначение a∧b{\displaystyle a\land b}, рекомендованное стандартом ISO 31-11, наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда &; последний, появившись ещё в I веке до н. э. как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия). Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком ⋅{\displaystyle \cdot } — как обычное умножение. Символ ⋀ (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930).

Обозначение для конъюнкции было использовано и в раннем языке программирования Алгол 60. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для конъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения и (с возможностью замены последнего на ключевое слово ); в языках Паскаль и Ада используется зарезервированное слово ; в языках C и C++ применяются обозначения для побитовой конъюнкции и для логической конъюнкции).

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что <1{\displaystyle 0<1}), оказывается, что (a∧b)=min(a,b).{\displaystyle (a\land b)\,=\,\min(a,b).} Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: (a∧b)=ab(mod⁡k){\displaystyle (a\land b)\,=\,ab\;(\operatorname {mod} k)} в случае k-значной логики, в которой множество значений истинности представлено начальным отрезком {,…,k−1}{\displaystyle \{0,\dots ,k-1\}} полугруппы N{\displaystyle \mathbb {N} } натуральных чисел).

Построение тавтологий

Для выяснения того, является ли данная формула тавтологией, в алгебре высказываний есть простой способ — построение таблицы истинности. В исчислении высказываний тавтологиями являются аксиомы (точнее — схемы аксиом), а также все формулы, которые можно получать из известных тавтологий с помощью заданных правил вывода (чаще всего это Modus ponens и правило подстановки). Проверка, является ли данная формула в исчислении высказываний тавтологией, более сложна, а также зависит от системы аксиом и доступных правил вывода.
Проблема определения того, является ли произвольная формула в логике предикатов тавтологией, алгоритмически неразрешима.

Интерпретация

В классическом случае интерпретация формул логики первого порядка задается на модели первого порядка, которая определяется следующими данными:

• Несущее множество D{\displaystyle {\mathcal {D}}},
• Семантическая функция σ{\displaystyle \sigma }, отображающая
  • каждый n{\displaystyle n}-арный функциональный символ f{\displaystyle f} из F{\displaystyle {\mathcal {F}}} в n{\displaystyle n}-арную функцию σ(f)D×…×D→D{\displaystyle \sigma (f)\colon \,{\mathcal {D}}\times \ldots \times {\mathcal {D}}\rightarrow {\mathcal {D}}},
  • каждый n{\displaystyle n}-арный предикатный символ p{\displaystyle p} из P{\displaystyle {\mathcal {P}}} в n{\displaystyle n}-арное отношение σ(p)⊆D×…×D{\displaystyle \sigma (p)\subseteq {\mathcal {D}}\times \ldots \times {\mathcal {D}}}.

Обычно принято отождествлять несущее множество D{\displaystyle {\mathcal {D}}} и саму модель, подразумевая неявно семантическую функцию, если это не ведет к неоднозначности.

Предположим, s{\displaystyle s} — функция, отображающая каждую переменную в некоторый элемент из D{\displaystyle {\mathcal {D}}}, которую мы будем называть подстановкой. Интерпретация ts{\displaystyle \!]_{s}} терма t{\displaystyle t} на D{\displaystyle {\mathcal {D}}} относительно подстановки s{\displaystyle s} задается индуктивно:

1. xs=s(x){\displaystyle \!]_{s}=s(x)}, если x{\displaystyle x} — переменная,
2. f(x1,…,xn)s=σ(f)(x1s,…,xns){\displaystyle \!]_{s}=\sigma (f)(\!]_{s},\ldots ,\!]_{s})}

В таком же духе определяется отношение истинности ⊨s{\displaystyle \models _{s}} формул на D{\displaystyle {\mathcal {D}}} относительно s{\displaystyle s}:

• D⊨sp(t1,…,tn){\displaystyle {\mathcal {D}}\models _{s}p(t_{1},\ldots ,t_{n})}, тогда и только тогда, когда σ(p)(t1s,…,tns){\displaystyle \sigma (p)(\!]_{s},\ldots ,\!]_{s})},
• D⊨s¬ϕ{\displaystyle {\mathcal {D}}\models _{s}\neg \phi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } — ложно,
• D⊨sϕ∧ψ{\displaystyle {\mathcal {D}}\models _{s}\phi \land \psi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } и D⊨sψ{\displaystyle {\mathcal {D}}\models _{s}\psi } истинны,
• D⊨sϕ∨ψ{\displaystyle {\mathcal {D}}\models _{s}\phi \lor \psi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } или D⊨sψ{\displaystyle {\mathcal {D}}\models _{s}\psi } истинно,
• D⊨sϕ→ψ{\displaystyle {\mathcal {D}}\models _{s}\phi \to \psi }, тогда и только тогда, когда D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } влечет D⊨sψ{\displaystyle {\mathcal {D}}\models _{s}\psi },
• D⊨s∃xϕ{\displaystyle {\mathcal {D}}\models _{s}\exists x\,\phi }, тогда и только тогда, когда D⊨s′ϕ{\displaystyle {\mathcal {D}}\models _{s’}\phi } для некоторой подстановки s′{\displaystyle s’}, которая отличается от s{\displaystyle s} только значением на переменной x{\displaystyle x},
• D⊨s∀xϕ{\displaystyle {\mathcal {D}}\models _{s}\forall x\,\phi }, тогда и только тогда, когда D⊨s′ϕ{\displaystyle {\mathcal {D}}\models _{s’}\phi } для всех подстановок s′{\displaystyle s’}, которые отличается от s{\displaystyle s} только значением на переменной x{\displaystyle x}.

Формула ϕ{\displaystyle \phi } истинна на D{\displaystyle {\mathcal {D}}} (что обозначается как D⊨ϕ{\displaystyle {\mathcal {D}}\models \phi }), если D⊨sϕ{\displaystyle {\mathcal {D}}\models _{s}\phi } для всех подстановок s{\displaystyle s}. Формула ϕ{\displaystyle \phi } называется общезначимой (что обозначается как ⊨ϕ{\displaystyle \models \phi }), если D⊨ϕ{\displaystyle {\mathcal {D}}\models \phi } для всех моделей D{\displaystyle {\mathcal {D}}}. Формула ϕ{\displaystyle \phi } называется выполнимой, если D⊨ϕ{\displaystyle {\mathcal {D}}\models \phi } хотя бы для одной D{\displaystyle {\mathcal {D}}}.

Классическая логика

В классическом исчислении высказываний свойства дизъюнкции определяются с помощью аксиом. Классическое исчисление высказываний может быть задано разными системами аксиом, и некоторые из них будут описывать свойства дизъюнкции. Один из самых распространённых вариантов включает 3 аксиомы для дизъюнкции:

• a→a∨b{\displaystyle a\to a\lor b}
• b→a∨b{\displaystyle b\to a\lor b}
• (a→c)→((b→c)→((a∨b)→c)){\displaystyle (a\to c)\to ((b\to c)\to ((a\lor b)\to c))}

С помощью этих аксиом можно доказать другие формулы, содержащие операцию дизъюнкции

Обратите внимание, что в классическом исчислении высказываний не происходит вычисления результата по значениям операндов (как в булевой алгебре), а требуется доказать формулу как единое целое на основе аксиом и правил вывода.

Литература

• Каймин В.А. Информатика. Учебник для студентов. М.: ИНФРА-М, 1998-2009.
• Каймин В.А. Информатика. Учебник для поступающих. М.: Проспект, 2009.
• Каймин В.А. Информатика. Пособие к экзаменам. М.: РИОР, 2008.
• Иван Братко Алгоритмы искусственного интеллекта на языке PROLOG = Prolog Programming For Artificial Intelligence. — М.: «Вильямс», 2004. — С. 640. — ISBN 0-201-40375-7

Хант Э. Искусственный интеллект = Artificial intelligence / Под ред. В. Л. Стефанюка. — М.: Мир, 1978. — 558 с.

К. Дж. Дейт Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: «Вильямс», 2006. — С. 1328. — ISBN 0-321-19784-4

Булева алгебра

Определение.
Логическая функция MIN в двухзначной (двоичной) логике называется конъюнкция (логи́ческое «И», логи́ческое умноже́ние или просто «И»).

Правило: результат равен наименьшему операнду.

Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества {,1}{\displaystyle \{0,1\}}. Результат также принадлежит множеству {,1}{\displaystyle \{0,1\}}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ,1{\displaystyle 0,1} может использоваться любая другая пара подходящих символов, например false,true{\displaystyle false,true} или F,T{\displaystyle F,T} или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, true>false{\displaystyle true>false}, при цифровом обозначении старшинство естественно 1>{\displaystyle 1>0}.
Правило: результат равен 1{\displaystyle 1}, если все операнды равны 1{\displaystyle 1}; во всех остальных случаях результат равен {\displaystyle 0}.

Таблицы истинности:
для бинарной конъюнкции

для тернарной конъюнкции

Конъюнкция коммутативна, ассоциативна и дистрибутивна по отношению к слабой дизъюнкции.

Неклассические логики

Модальная логика

• Модальность
• Алетические модальности (алетическая модальность, алетическая модальная логика, алетические модальные логики)
• Деонтические модальности (деонтическая модальность, деонтическая модальная логика, деонтические модальные логики)
• Эпистемологические модальности (эпистемологическая модальность, эпистемологическая модальная логика, эпистемологические модальные логики)
• Временные модальности (временная модальность, временные модальные логики, временная модальная логика)
• Строгая импликация
• Материальная импликация

Недедуктивные логические теории

• Индуктивная логика
• Вероятностная логика
• Логика решений
• Логика нечётких понятий (логика нечётких множеств, нечёткая логика)
• Аналогия (умозаключение по аналогии).

Другие неклассические логики

• Категориальная логика
• Комбинаторная логика — это логика, которая заменяет переменные функциями с целью прояснить такие интуитивные операции с переменными, как подстановка. Построенная на базе комбинаторной логики система арифметики содержит все частично рекурсивные функции и избегает гёделевской неполноты.
• Кондициональная логика (условная логика). Её предмет — истинность условных предложений (в частности, сослагательного наклонения). Логика контрафактических утверждений.

Утрата специфики

Распространение идей многозначной логики в различных её вариантах (в том числе, символизированных), а затем — идей абстрактных типов данных в теоретическом программировании проблематизировало «изнутри» специфику истинности как области значений логических функций, включающих лишь два возможных значения. Так, аппарат бесконечнозначной логики Лукасевича—Тарского практически неотличим от аппарата теории вероятностей, а в теории типов данных логический (булев) тип ничем особенным не отличается от прочих ни с операторной точки зрения, ни с точки зрения машинной реализации.

С другой стороны, новые разделы и версии символической логики (например, интуиционистская логика, интенциональная логика, деонтическая логика) вышли далеко за пределы силлогистики и исследования истинности в узком смысле и охватили собой многие другие разделы логики.

В настоящее время термин «формальная логика» утратил специфическое значение и применяется (вне контекста истории науки) как синоним символической, или математической логики. «Традиционной» (в противоположность «современной») формальной логикой могут называть те же разделы логики, изложенные без применения математического аппарата.

Умозаключение

Умозаключение – это форма мышления, в которой из двух или нескольких суждений, называемых посылками, вытекает новое суждение, называемое заключением (выводом). Например:

• Все животные нуждаются в корме.
• Лошади – это животные.
• Лошади нуждаются в корме.

В приведенном примере первые два суждения являются посылками, а третье – выводом (умозаключением).

Имейте в виду, что посылки должны быть не только истинными суждениями, но и связанными между собой.

Умозаключения делятся на три вида:дедуктивные, индуктивные и умозаключения по аналогии.

Дедуктивные умозаключения (дедукция) (от лат. deductio — «выведение») – это умозаключения, в которых из общего правила делается вывод для частного случая. Например:

• Все хищники питаются мясом.
• Львы – это хищники.
• Львы питаются мясом.

Основное достоинство дедукции заключается в достоверности ее выводов. Известный персонаж Шерлок Холмс пользовался дедуктивным методом при раскрытии преступлений.

Однажды, объясняя доктору Ватсону суть дедуктивного метода, он привел такой пример. Около убитого полковника была найдена выкуренная сигара, вследствие чего сыщики Скотленд-Ярда решили, что именно он выкурил ее перед смертью. Но Холмс отвергает эту версию на основании того, что полковник носил большие усы, а сигара выкурена до конца.

Иначе говоря, если бы ее курил убитый, то он обязательно бы подпалил свои усы. Следовательно, делает дедуктивное умозаключение Холмс, сигару выкурил другой человек.

Все дедуктивные умозаключения называются силлогизмами (от греч. sillogismos – «подсчитывание, подытоживание, выведение следствия»).

Индуктивные умозаключения (индукция) (от лат. inductio — «наведение») – это умозаключения, в которых из нескольких частных случаев выводится общее правило. Например:

• Петя любит играть.
• Ваня любит играть.
• Настя любит играть.
• Петя, Ваня и Настя – дети.
• Все дети любят играть.

Умозаключения по аналогии (аналогия) (от греч. analogia — «соответствие») – это умозаключения, в которых на основе сходства предметов (объектов) в одних признаках делается вывод об их сходстве и в других признаках. Например:

• Мотоциклист Вася обожает свой мотоцикл, быструю езду, ровную дорогу, и недолюбливает машины.
• Мотоциклист Коля обожает свой мотоцикл, быструю езду и ровную дорогу.
• Вероятно, Коля недолюбливает машины.

Помните, что выводы аналогии и индукции всегда вероятностны.

Итак, вы ознакомились с определением науки логики, а также поняли, что собой представляет логическое мышление.

Теперь вам осталось совсем немного, а именно, узнать 4 основных закона логики. После этого вы сможете развивать логическое мышление и определять логические ошибки своих собеседников.