Успешное подключения к БД.

-------------------
Вы знаете, как устроен наш мир?



---Load files---
Совет: если изображения отображаются неправильно, попробуйте очистить кеш браузера!
Поиск на странице - нажмите "Ctrl+F", Поиск на сайте - поле ввода "Яндекс-Найти" на "шапке",
Поиск в интернете - 1) выделите текст, 2) нажмите правую клавишу мыши и 3) выберите поисковик.

С О Д Е Р Ж А Н И Е

------- Тимин В.А. (mail: timinva@yandex.ru) Дата последней загрузки: November 09 2017. -------
Ссылка на этот материал: algebra_logiki.htm)
Математическая логика

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

1      Применение скобок

Общие способы записи выражений и применения скобок можно просмотреть во "Введении" по адресу 000100oboznachyeniya.htm.

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

При записи выражений (функций, формул, уравнений) обычно применяются скобки. Роль скобок в выражении может быть различной.

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

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

F(a, b) = (a + b).

Такую форму записи называют "операцией". При строгой форме записи выражение для записи операции необходимо заключать в скобки.

При соблюдении строгом правилам записи выражений получаются плохо читаемые выражения. Для упрощения выражений применяются правила, упрощающие вид получающихся выражений. Это достигается удалением скобок в выражениях и определения приоритетов операций. Такие упрощения выполняются в соответствии с договоренностями насчет использования скобок и приоритетов порядка выполнения операций. В математической логике можно применять следующие договоренности.

Пусть F – некоторое выражение. Скобки вокруг F можно опускать, если F имеет вид: 0, 1, Ø0, Ø1, x, Øx, Ø(F), где x - произвольная булева переменная, F - произвольная формула булевой алгебры. Иначе скобки опускать нельзя.

Можно опускать также самые внешние скобки в выражении. Например:

(a + b) ~ a + b.

На практике опускают еще больше скобок, если это не затрудняет понимание, и есть договоренность о том, в каком порядке какие операции вычисляются. Обычно первой вычисляется операция "&", потом "" и "", потом все остальные. Если рядом идут операции одного приоритета, то вычисляются подряд слева направо.

Еще одним способом упрощения записи является цепочка равенств из выражений вида

F1(…) = F2(…) = … =F3(…).

Такая запись означает, что любые два выражения из этой цепочки равны:

Fi(…) = Fj(…).

2      Математическая логика

Аристотель определял два вида логики:
1. Формальная логика - любое высказывание либо истинное, либо ложное.

2. Диалектическая логика - любое высказывание и истинное и ложное.

3. Существует еще и нечеткая логика.

Первое – это математика в конкретной теории, второе – физика, третье – статистика.

(Материал из Википедии — свободной энциклопедии)

Математи́ческая ло́гика (теоретическая логика, символическая логика) — раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен.»[1] Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков)[2] Это определение соответствует определению С. К. Клини: математическая логика — это «логика, развиваемая с помощью математических методов».[3] Так же А. А. Марков определяет современную логику «точной наукой, применяющей математические методы».[4] Все эти определения не противоречат, а дополняют друг друга.

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

Важную роль в математической логике играют понятия дедуктивной теории и исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы A, синтаксически связанные некоторым заранее определённым способом с конечными наборами A1, … An выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы A и (A B), то выводима и формула B.

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

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

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

2.1     Разделы математической логики

См. также

2.2     Алгебра высказываний и предикатов.

 

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

Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения информации, семантического смысла знаний.

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

Рассмотрим примеры:

1.      Москва – столица Российской Федерации.

2.      Житель города Нальчика.

3.      5 – 9 + 8

4.      5 – 9  + 8 = 4

5.      В пятую неделю зимы выпал снег.

6.      На Юге Африки живут пингвины.

Высказывание должно быть однозначно истинным или ложным, поэтому высказываниями являются только утверждения 1, 4 ,6.

 

Не является высказыванием и парадокс лжеца (Эвбулид, учитель Демосфена, около 350 лет до н.э.): «То, что я сейчас утверждаю, ложно», ибо если оно истинно, то оно ложно, а если допустить, что оно ложно, то оно истинно. Это неопределённая высказывательная форма.

Аналогичный пример принадлежит Геделю (1931): «То, что утверждается в этом предложении, не может быть доказано». Если его можно доказать, то его нельзя доказать, а если его можно опровергнуть, то его можно доказать. Предложения такого рода не могут быть доказаны в пределах данного языка алгебры логики.

Предикат – выражение с логическими переменными, имеющее смысл при любых допустимых значениях этих переменных.

Выражения: х > 5, x > y – предикаты.

                      7>5 – высказывание.

Логической (булевой) функцией f(x) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Множество логических переменных x, y Î X с определенными над ним операциями: \overline{x}отрицания или инверсии, x Ú yлогического сложения или дизъюнкции, x Ù yлогического умножения или конъюнкции называется алгеброй предикатоввысказываний), если эти операции удовлетворяют определенным аксиомам.

2.3     Логические операции

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество B, состоящее всего из двух элементов:

B = { Ложь, Истина }.

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

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквивалентность \leftrightarrow («тогда и только тогда, когда»), импликация \rightarrow («следовательно»), сложение по модулю два \oplus («исключающее или»), штрих Шеффера \mid, стрелка Пирса \downarrow и другие.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция \neg приобретает смысл вычитания из единицы (НЕ – NO); Ú, + — немодульного сложения (ИЛИ – OR); Ù, & — умножения (И - AND); \leftrightarrow, ~ — равенства; \oplus — в буквальном смысле сложения по модулю 2 (исключающее ИЛИ — XOR); \mid — непревосходства суммы над 1 (то есть A \mid B  = (A + B) <= 1).

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

2.4     Литература

  • Марков А. А.. Элементы математической логики. М.: Изд-во МГУ, 1984.
  • Новиков П. С. Элементы математической логики. 2-ое изд. М.: Наука, 1973. — 400 с.
  • Столл Р. Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. — 232 с.
  • Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967. 508 с.
  • Шенфилд Дж. Математическая логика. М.: Наука, 1975.
  • Адян С. И., Математическая энциклопедия, М.: «Советская энциклопедия», т.3, с. 568, 571.
  • Кондаков Н. И., Логический словарь-справочник, М.: «Наука», 1975, с. 259.
  • Клини С. К., Математическая логика, М., 1973, с.12.
  • Марков А. А., Большая советская энциклопедия, Изд. 3, Предмет и метод современной логики.
  • Н. К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов (электронные версии трех частей книги).
  • Логика математическая.

3      Логическое высказывание

Логическое высказывание — упрощение термина «Суждение» из формальной логики, используется в математической логике. Высказыванием является повествовательное предложение, которое формализует некоторое выражение мысли. Это утверждение, которому всегда можно поставить в соответствие одно из двух логических значений: ложь (0, ложно, false) или истина (1, истинно, true). Логическое высказывание принято обозначать заглавными латинскими буквами.

Высказывательной формой называется логическое высказывание, в котором один из объектов заменён переменной. При подстановке вместо переменной какого-либо значения высказывательная форма превращается в высказывание. Пример: A(x) = «В городе x идет дождь.» A — высказывательная форма, x — объект.

Высказывание обычно имеет только одно логическое значение. Так, например, «Париж - столица Франции» — высказывание, а «На улице идет дождь» — не высказывание. Аналогично, «5>3» — высказывание, а «2+3» — не высказывание. Как правило, высказывания обозначают маленькими латинскими буквами.

3.1     Виды высказываний

Логические высказывания принято подразделять на два вида: элементарные логические высказывания и составные логические высказывания.

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

Логическая связка — это любая логическая операция над высказыванием. Например, употребляемые в обычной речи слова и словосочетания "не", "и", "или", "если... , то", "тогда и только тогда" являются логическими связками.

Элементарные логические высказывания — это высказывания не относящиеся к составным.

Примеры: "Петров — врач", "Петров — шахматист" — элементарные логические высказывания. "Петров — врач и шахматист" - составное логическое высказывание, состоящие из двух элементарных высказываний, связанных между собой при помощи связки "и".

3.2     Связь с математической логикой

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

Пусть p — высказывание. Если оно истинно, то пишут | p | = 1, если ложно, то | p | = 0.

Тождественно истинное высказывание обозначают символом 1, тождественно ложное — символом 0.

Существуют также многозначные логики (Яна Лукасевича, С. Клини и др.).

3.3     Основные операции над логическими высказываниями

Отрицание логического высказывания — логическое высказывание, принимающее значение "истинно", если исходное высказывание ложно, и наоборот.

Конъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны.

Дизъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.

Импликация двух логических высказываний A и B — логическое высказывание, ложное только тогда, когда B ложно, а A истинно.

Равносильность (эквивалентность) двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.

Кванторное логическое высказывание с квантором всеобщности ("xA(x)) — логическое высказывание, истинное только тогда, когда для каждого объекта x из заданной совокупности высказывание A(x) истинно.

Кванторное логическое высказывание с квантором существования ($xA(x)) — логическое высказывание, истинное только тогда, когда в заданной совокупности существует объект x, такой, что высказывание A(x) истинно.

3.4     Литература, ссылки

  • Карпенко, А. С. Современные исследования в философской логике // Логические исследования. Вып. 10. - М.: Наука, 2003. ISBN 5-02-006257-X - С. 61-93.
  • Крипке, С. А. Витгенштейн о правилах и индивидуальном языке / Пер. В.А. Ладова, В.А. Суровцева. Под общ. ред. В.А. Суровцева. - Томск: Изд-во Том. ун-та, 2005. - 152 с. - (Библиотека аналитической философии). ISBN 5-7511-1906-1
  • Курбатов, В. И. Логика. Систематический курс. – Ростов-на-Дону: Феникс, 2001. - 512 c. ISBN 5-222-01850-4
  • Шуман, А. Н. Современная логика: теория и практика. - Минск: Экономпресс, 2004. - 416 с. ISBN 985-6479-35-5
  • Макарова, Н. В. Информатика и ИКТ. - Санкт-Петербург: Питер Пресс, 2007 ISBN 978-5-91180-198-4 - С. 343-345.

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

(Материал из Википедии — свободной энциклопедии)

Создателем булевой алгебры является был английский математик и логик Джордж Буль (1815-1864). В работах "The mathematical analysis of logic..." ("Математический анализ логики") 1847 года и "An investigation of the laws of thought..." ("Исследование законов мышления") от 1854 года Джордж Буль заложил основы математической логики.

В математике имеется особый класс множеств – множество (логических) высказываний и множество его значений, состоящее из двух элементов – «истина» (или 1) и «ложь» (или 0). Эта алгебра является формальным инструментом познания в математике. Любое знание определяется как некое высказывание, имеющее значение «истина». Методом получения новых знаний (познания) является доказательство. Доказательство есть последовательность логически следующих друг из друга логических высказываний, последнее высказывание которой есть истина. Кстати, любое отношение порядка между подмножествами и элементами множества есть логическое высказывание.

Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:

Ù

0

1

 

Ú

0

1

 

a

0

1

0

0

0

 

0

0

1

 

¬a

1

0

1

0

1

 

1

1

1

 

 

 

 

Эта булева алгебра наиболее часто используется в логике, так как является точной моделью классического исчисления высказываний. В этом случае 0 называют ложью, 1 — истиной. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.

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

Множество всех подмножеств данного множества S образует булеву алгебру относительно операций È(объединение), ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.

Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так: A = { e R : e2 = e, ex = xe, x R }, тогда множество A будет булевой алгеброй с операциями e f := e + fef и e f := ef.

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

Задача упрощения логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов) эквивалентному выражению. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь).

4.1     Представления булевых алгебр

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

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

4.2     Аксиоматизация

В 1933 г. американский математик Хантингтон предложил следующую аксиоматизацию для булевых алгебр:

  1. Аксиома коммутативности: x + y = y + x.
  2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
  3. Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

  1. Аксиома коммутативности: x + y = y + x.
  2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
  3. Уравнение Роббинса: n(n(x + y') + n(x + n(y))) = x.

Этот вопрос оставался открытым с 30-х годов и был любимым вопросом Тарского и его учеников.

В 1996 г. Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

4.3     Аксиомы булевой алгебры

Булевой алгеброй называется непустое множество A с двумя бинарными операциями \land(аналог конъюнкции), \lor(аналог дизъюнкции), унарной операцией \lnot(аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

 a \lor (b \lor c) = (a \lor b) \lor c

 a \land (b \land c) = (a \land b) \land c

ассоциативность сочетательность

 a \lor b = b \lor a

 a \land b = b \land a

коммутативность переместительность

 a \lor (a \land b) = a

 a \land (a \lor b) = a

законы поглощения

 a \lor (b \land c) = (a \lor b) \land (a \lor c)

 a \land (b \lor c) = (a \land b) \lor (a \land c)

дистрибутивность распределительность

 a \lor \lnot a = 1

 a \land \lnot a = 0

комплементность дополнительность (свойства отрицаний)

\begin{align}
& a+(b+c)=(a+b)+c  & a(bc)=(ab)c  \\
& a+b=b+a          & ab=ba        \\   
& a+ab=a           & a(a+b)=a     \\
& a+bc=(a+b)(a+c)  & a(b+c)=ab+ac \\
& a+\bar{a}=1      & a\bar{a} = 0
\end{align}

Первые три аксиомы означают, что (A, \land, \lor) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

 a \lor a = a;

 a \land a = a ;

Идемпотентность

 a \lor 0 = a ;

 a \land 1 = a ;

свойства констант

 a \lor 1 = 1 ;

 a \land 0 = 0 ;

 \lnot 0 = 1 ;

 \lnot 1 = 0 ;

 \lnot (a \lor b) = \lnot a \land \lnot b;

 \lnot (a \land b) = \lnot a \lor \lnot b;

законы де Моргана

 \lnot \lnot a = a .

 

инволютивность отрицания

4.4     Некоторые свойства логических операций

    • a \lor(\lnot a \land b) = a \lor b (Закон Блейка-Порецкого)
    • a \land(\lnot a \lor b) = a \land b (Закон Блейка-Порецкого)
    •  (a \lor b)\land(\lnot a \lor b)=b (Склеивание)
    •   (a \land b) \lor (\lnot a \land b)=b (Склеивание)
    • x \oplus x = 0.
    • x ~ x = x \rightarrow x = 1.
    • x \oplus 0 = x.
    • x \oplus 1 = x \rightarrow 0 = x ~ 0 = x \mid x = x \downarrow x = \negx.
    • x \oplus y = (x\land\bar y)\lor (\bar x\land y)= (x\lor y)\land (\bar x\lor\bar y).
    • x ~ y = Ø(x \oplus y)  = (x\land y)\lor (\bar x\land \bar y)= (x\lor\bar y)\land (\bar x\lor y).
    • x y = Øx Ú y = ((x\land y)\oplus x)\oplus 1.
    • x | y = Ø(x Ù y) = Øx Ú Øy.
    • x ¯ y = Ø(x Ú y) = Øx Ù Øy. 

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки.

Всего возможно существование 4 булевых операций с одним аргументом. Это тождественная функция,  отрицание, ноль и единица:

x

0

1

x

Øx

0

0

1

0

1

1

0

1

1

0

Функция "0" всегда принимает значение 0, поэтому неважно, что имеется в виду: функция или значение; и можно применить одно и то же обозначение. То же самое относится к функции "1". Тождественная функция по значению всегда совпадает со своим аргументом, поэтому можно применять одно и то же обозначение и для аргумента, и для функции. Единственная нетривиальная функция - отрицание. Она изменяет значение параметра на противоположное: ~0 = 1, ~1 = 0. Знак "~" является знаком унарной операции и обозначает эту функцию.

Наиболее полезная из этих функции – отрицание.

Другие названия этой функции: "инверсия", "обращение", "НЕ", "логическое НЕ".

Другие обозначения этой функции: .

Всего возможно существование 16 логических двухместных операций, из них 6 – тривиальных: 0, 1, , x, Øx, y, Øy. Некоторые из них всегда совпадают по значению с булевой константой, булевой переменной или функцией только от одной из двух переменных. Поскольку эти операции могут быть упрощены до булевой величины, переменной или унарной операции, то нет смысла вводить для них какое-то более сложное обозначение. Остальные 10 функций не упрощаются.

В заключение приведем сводную таблицу всех бинарных логических операций:

x

y

0

1

x

y

Øx

Øy

xy

x&y

xy

x<y

x>y

xy

x|y

xy

xy

xy

0

0

0

1

0

0

1

1

0

0

1

0

0

0

1

1

1

1

0

1

0

1

0

1

1

0

1

0

0

1

0

1

1

0

1

0

1

0

0

1

1

0

0

1

1

0

0

0

1

1

1

0

0

1

1

1

0

1

1

1

0

0

1

1

0

0

0

0

0

1

1

1

4.5     Альтернативные обозначения логических операций

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

1. Для логического отрицания применяются следующие обозначения: -, ù, Ø, ¬, n, Not, НЕ, (верхнее подчеркивание).

2. Для логического сложения (дизъюнкции): Ú, +; Or, ИЛИ.

3. Для логического сложения по модулю 1: Å.

4. Для логического умножения (конъюнкции): &, Ù,  ·; And, И.

5. Для логического вычитания: /, {все логические отрицания  в двухместной записи}

6. Для логического следования (импликация): =>, ->, →, Þ.

7. Для логической эквивалентности: =, ~, Equ.

8. Штрих Шеффера: |, ИЛИ-НЕ.

9. Стрелка Пирса: ¯, И-НЕ.

10. Для некоммутативных операции с несимметричным символом применяются обозначения с зеркальным изображением символа.

4.6     Свойства операций

4.6.1       Коммутативные операции.

Коммутативными называют операции, которые позволяют переставлять местами свои операнды, не меняя операцию. По схеме: x + y = y + x, где + - некоторая операция.

x & y = y & x

x y = y x

x y = y x

x y = y x

x y = y x

x | y = y | x

Остальные операции также позволяют переставлять операнды, но с заменой на другую операцию:

x > y = y < x

x y = y x

Как видите, и в булевой алгебре операции сложения  и умножения & позволяют переставлять свои слагаемые.

Можно использовать простое мнемоническое правило: при перестановке операндов логической операции местами надо повернуть знак операции вокруг веритикальной оси. Если получится другой знак логической операции, взять его. Если получится тот же знак, взять его. Если получится несуществующий знак (для операции &), то оставить прежний знак.

4.6.2       Ассоциативные операции.

Ассоциативными называют операции, которые можно выполнять в произвольном порядке. По схеме: (x + y) + z = x + (y + z), где + - некоторая операция. Здесь приведена программа на языке C, позволяющая увидеть таблицу истинности всех 16 бинарных логических операций и проверить их ассоциативность путем перебора вариантов.

Проверка показывает ассоциативность всего лишь для 4 операций "&", "", "", "" из 10 нетривиальных.

(x & y) & z = x & (y & z)

(x y) z = x (y z)

(x y) z = x (y z)

(x y) z = x (y z)

Из комутативности и ассоциативности этих четырех операций следует, что если мы имеем много переменных подряд, соединенных такой операцией, то переменные можно переставлять в любом порядке, а значит скобки для указания порядка не обязательны:

(a & b) & (c & d) = a & d & c & b.

4.6.3       Дистрибутивные операции.

Дистрибутивной называют пару операций, для которых работает схема раскрытия скобок, характерная для сложения и умножения в арифметике:

x * (y + z) = (x * y) + (x * z) и

(x + y) * z = (x * z) + (y * z),

где * и + - некоторые логические операции.

Первую схему будем называть левой дистрибутивностью, вторую схему - правой дистрибутивностью, а если срабатывают обе схемы, то будем говорить о полной дистрибутивности или просто дистрибутивности.

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

Из полученных правил наибольший практический интерес представляют следующие:

x & (y z) = (x & y) (x & z)

(x y) & z = (x & z) (y & z)

x (y & z) = (x y) & (x z)

(x & y) z = (x z) & (y z)

x & (y z) = (x & y) (x & z)

(x y) & z = (x & z) (y & z)

Как видите, дистрибутивность между логическим умножением и сложением в алгебре логики такая же как в обычной алгебре (где она называется "распределительным законом"). Обратите внимание, что и для операций "" и "&" можно раскрывать скобки таким же способом. Причем обе операции оказываются равноправны: можно раскрывать скобки когда в них стоит "&", а вне скобок - "", а можно и в обратной ситуации - когда внутри скобок стоит "".

4.6.4       Двойственные функции.

Логические функции f и g называются двойственными, если

f(~x1, ~x2,...,~xN) = ~g(x1, x2,..., xN).

Кратко это будем обозначать так: "f" * "g". Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Ниже приведен список двойственных функций для всех унарных и бинарных операций.

"0" и "1"

"x" и "x"

"~" и "~"

"&" и ""

"" и ""

"|" и ""

"<" и ""

">" и ""

Кроме двойственных, существуют самодвойственные функции. Это - логическая функция, которая двойственна самой себе:

f(~x1, ~x2,...,~xN) = ~f(x1, x2,..., xN).

4.6.5       Обратные операции.

Формулы обратных операций позволяют убирать знак отрицания в формулах вида Ø(x # y) путем замены некоторой операции # на другую операцию:

Ø (x & y) = x | y

Ø (x | y) = x & y

Ø (x > y) = x y

Ø (x y) = x > y

Ø (x < y) = x y

Ø (x y) = x < y

Ø (x y) = x y

Ø (x y) = x y

Ø (x y) = x y

Ø (x y) = x y

4.7     Минимизация количества видов использованных операций

4.7.1       Сведение к "&", "Ø" и "".

Любую бинарную логическую операцию можно свести к операциям "&", "Ø" и "":

x > y = x & Øy

x < y = ~x & y

x y = (x & Øy) (~x & y)

x y = Øx & Øy = Ø (x y)

x y = (x & y) (Øx & Øy)

x y = x Øy

x y = Øx y

x | y = Øx Øy = Ø (x & y)

Применяя эти формулы, можно всякую формулу, представленную в виде комбинации бинарных логических операций, свести к функции, в которой есть только операции "&", "~" и "".

4.7.2       Сведение к "&" и "Ø".

Любую бинарную логическую операцию можно свести к операциям "&" и "Ø". Для этого достаточно свести ее к операциям "&", "" и "Ø", а потом исключить и операцию "" с помощью правила:

x y = Ø (Øx & Øy)

4.7.3       Сведение к "" и "Ø".

Любую бинарную логическую операцию можно свести к операциям "" и "Ø". Для этого достаточно свести ее к операциям "&", "" и "Ø", а потом исключить и операцию "&" с помощью правила:

x & y = Ø (Øx Øy)

4.7.4       Сведение к "|".

Любую бинарную логическую операцию можно свести к единственной операции: штриху Шеффера. Для этого достаточно свести ее к операциям "" и "Ø", а потом преобразовать эти операции к операции "|" по правилам:

Øx = x | x

x y = (x | x) | (y | y)

4.7.5       Сведение к "".

Любую бинарную логическую операцию можно свести к единственной операции: стрелке Пирса. Для этого достаточно свести ее к операциям "&" и "Ø", а потом преобразовать эти операции к операции "" по правилам:

Øx = x x

x & y = (x x) (y y)

4.7.6       Сведение к "" и "&".

Любую бинарную или унарную логическую операцию можно свести к операциям " и "&":

Øx = x 1

x y = x y (x & y) 1

x y = x y (x & y)

x | y = (x & y) 1

x y = x y 1

x > y = x (x & y)

x y = x (x & y) 1

x < y = y (x & y)

4.8     Нормальные формы логических функций

4.8.1        Совершенная дизъюнктивная нормальная форма

4.8.2        Совершенная конъюнктивная нормальная форма

4.8.3        Полином Жегалкина.

Это - еще один способ выразить произвольную булеву функцию через бинарные операции. Мы уже знаем, что произвольную булеву функцию можно выразить через &, и ~ в виде СДНФ. Мы также знаем, что и ~ можно выразить через & и :

x y = x y (x & y)

~x = x 1

Применив эти формулы, мы всякую булеву функцию выразим через операции & и .

Дальше мы можем раскрыть все скобки, кроме самого последнего уровня, применяя правила дистрибутивности (в точной аналогии с тем, как это делалось в школе с раскрытием скобок и приведением подобных членов):

x & (y z) = (x & y) (x & z)

(x y) & z = (x & z) (y & z).

В результате получится формула вида:

(xa & xb & ...) ... (xc & xd & ...)

или вида:

(xa & xb & ...) ... (xc & xd & ...) 1

где в скобках стоят те или иные наборы аргументов, объединенные операцией &, а сами скобки объединены операцией . После этого формулу можно сократить, убрав повторяющиеся элементы внутри скобок с помощью законов поглощения

a & a = a, a & 1 = a, 1 & a = a

Затем выполним дополнительное сокращение, убрав одинаковые скобки с помощью законов поглощения

a a = 0, a 0 = a, 0 a = a.

В результате получится формула, которая и называется полиномом Жегалкина

4.9     Литература

 

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

(Не следует путать с булевой алгеброй!).

Материал из Википедии — свободной энциклопедии. Смотрите также: http://psi-logic.narod.ru/bool/bool.htm.

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан Б. Порецким в Казанском государственном университете.

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

Базовыми элементами, которыми оперирует алгебра логики являются высказывания. Высказывания строятся над множеством {B, \lnot, \land, \lor, 0, 1}, где 0 и 1 – константы алгебры, B — непустое множество,  над элементами которого определены три операции:

\lnot - отрицание (унарная операция),

\land, · -  конъюнкция (бинарная),

\lor, + - дизъюнкция (бинарная),

Константы — логический ноль 0 и логическая единица 1.

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например x1 Ú Øx2 Ú x4).

Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например x1 Ù Øx2 Ù x4).

Логической (булевой) функцией f(x) (предикатом) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Множество логических переменных x, y Î X с определенными над ним операциями: \overline{x}отрицания или инверсии, x Ú y логического сложения или дизъюнкции, x Ù yлогического умножения или конъюнкции называется алгеброй предикатоввысказываний), если эти операции удовлетворяют определенным аксиомам.

Три базовых операций предикатов (отрицания, дизъюнкции, конъюнкции) определяются таблицей истинности:

x

y

\overline{x}

x\land y

x\lor y

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

1

1

0

1

1

Такая таблица всех значений некоторой логической функции называется таблицей истинности. Всегда истинные формулы называют тавтологиями .

Свойства операции по отношению к логическим константам 0 и 1 определяются булевой алгеброй.

5.1     Основные аксиомы

1.      Аксиома двойного отрицания:

\overline{\overline{x}}=x

2.      Аксиомы коммутативности операндов (относительно операций дизъюнкции и конъюнкции):

x \land y = y\land x, x \lor y = y \lor x

3.      Аксиомы ассоциативности операций дизъюнкции и конъюнкции (относительно операндов):

(x \land y) \land z = x \land (y \land z), 
(x \lor y) \lor z = x \lor (y \lor z)

4.      Аксиомы одинаковых операндов:

x\land x = x, x \lor x = x

5.      Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):

x \land (x \lor y) = x, x \lor (x \land y) = x

6.      Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот):

x \land (y \lor z) = (x \land y) \lor (x \land z), x \lor (y \land z) = (x \lor y) \land (x \lor z)

7.      Аксиомы де Моргана (перенесения бинарной операции на операнды):

\overline{x\land y} = \overline{x}\lor\overline{y}, \overline{x\lor y}=\overline{x}\land\overline{y}

8.      Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):

x\land(y\lor\overline{y})=x, x\lor(y\land\overline{y})=x

9.      Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,

\overline{0}=1, \overline{1}=0, \overline{x}\lor x=1, \overline{x}\land x = 0

Первые восемь аксиом из этого списка и два соотношения из девятой инвариантны относительно взаимной замены  дизъюнкции на конъюнкцию. И только последние два соотношения девятой аксиомы отличают дизъюнкцию от конъюнкции.

Из этих аксиом следует ряд полезных соотношений, например,

x\land1=x,\\x\lor0=x,\\x\lor1=1,\\x\land0=0,\\ \overline{x}\lor x=1,\\ \overline{x}\land x=0

6      Логика высказываний

Материал из Википедии — свободной энциклопедии

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

6.1     Основные понятия

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

  1. Если P — пропозициональная переменная, то P — формула.
  2. Если A — формула, то \neg A— формула.
  3. Если A и B — формулы, то (A \to B), (A \wedge B)и (A \vee B)— формулы.
  4. Других соглашений нет.

Знаки \neg, \wedge, \veeи \to(отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

6.2     Правила построения формул логики высказываний

  1. Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
  2. Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1)\vee(Ф2)), ((Ф1)\wedge(Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

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

6.3     Истинностное значение

Оценкой пропозициональных переменных называется функция из множества всех пропозициональных переменных в множество {0, 1} (т.е. множество истинностных значений). Основной задачей логики высказываний является установление истинностного значения формулы, если дана оценка (т.е. определены истинностные значения входящих в неё переменных). Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок.

Оценка отрицания \neg pзадаётся таблицей:

p\!

\neg p

0\!

1\!

1\!

0\!

Значение двуместных логических связок \rightarrow(импликация), \vee(дизъюнкция) и \wedge(конъюнкция) определяются так:

p\!

q\!

p\rightarrow q

p \wedge q

p \vee q

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

1

1

1

1

1

6.4     Тождественно истинные формулы (тавтологии)

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

Законы де Моргана:

1)  \neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q);

2)  \neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q);

Закон контрапозиции:

(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p);

Законы поглощения:

1) p\vee(p\wedge q)\leftrightarrow p;

2) p\wedge(p\vee q)\leftrightarrow p;

Законы дистрибутивности:

1) p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r);

2) p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r).

6.5     Исчисление высказываний

Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

A_1 : A \rightarrow (B \rightarrow A);

A_2 : ((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)));

A_3 : A \wedge B \rightarrow A;

A_4 : A \wedge B \rightarrow B;

A_5 : A \rightarrow (B \rightarrow (A \wedge B));

A_6 : A \rightarrow (A \vee B);

A_7 : B \rightarrow (A \vee B);

A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C));

A_9 : \neg A \rightarrow (A \rightarrow B);

A_{10} : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A);

A_{11} : A\vee\neg A.

вместе с единственным правилом:

\frac{A \rightarrow B, A}{B}(Modus ponens)

Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

6.6     Ссылки

7      Логика первого порядка. Предикаты

Материал из Википедии — свободной энциклопедии

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

7.1     Основные определения

Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов \mathcal{F}и множества предикатных символов \mathcal{P}. С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные так и предикатные символы арности 0. Первые иногда выделяют в отдельное множество констант. Кроме того используются следующие дополнительные символы

  • Символы переменных (обычно x, y, z, x1, y1 ,z1, x2, y2, z2 и т. д.),
  • Пропозициональные связки: Ù, Ú, Ø, ®,
  • Кванторы: всеобщности " и существования $,
  • Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из \mathcal{P}и \mathcal{F}образуют Алфавит логики первого порядка. Более сложные конструкции определяются индуктивно:

  • Терм есть символ переменной, либо имеет вид f(t1, …, tn), где f — функциональный символ арности n, а t1, …, tn — термы.
  • Атом имеет вид p(t1, …, tn), где p — предикатный символ арности n,
  • Формула — это либо атом, либо одна из следующих конструкций: ØH, F1 Ú F2, , F1 Ù F2, F1 ® F2, "xF, $xF, где F, F1, F2 — формулы, а x — переменная.

Переменная x называется связанной в формуле F, если F имеет вид "xG либо $xG, или же представима в одной из форм ØH, F1 Ú F2, , F1 Ù F2, F1 ® F2, причем x уже связанна в H, F1 и F2. Если x не связанна в F, ее называют свободной в F. Формулу без свободных переменных называют замкнутой формулой, или предложением. Теорией первого порядка называют любое множество предложений.

7.2     Аксиоматика и доказательство формул

Система логических аксиом логики первого порядка состоит из аксиом исчисления высказываний дополненной двумя новыми аксиомами:

  • "xA ®  A[t / x],
  • A[t / x] ® $xA,

где A[t / x] — формула, полученная в результате подстановки терма t вместо переменной x в формуле A.

Правил вывода 2:

\frac{A, A \to B}{B}

  • Правило обобщения (GEN):

\frac{A}{\forall x A}

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

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

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

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

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

  • [[x]]s = s(x), если x — переменная,
  • [[f(t1, …, tn)]]s = s(f)([[x1]]s, …, [[xn]]s),

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

  • \mathcal{D}\models_s p(t_1,\ldots,t_n), тогда и только тогда, когда \sigma(p)( \![x_1]\!]_s,\ldots,\![x_n]\!]_s),
  • \mathcal{D}\models_s \neg\phi, тогда и только тогда, когда \mathcal{D}\models_s \phi— ложно,
  • \mathcal{D}\models_s \phi\land\psi, тогда и только тогда, когда \mathcal{D}\models_s \phiи \mathcal{D}\models_s \psiистинны,'
  • \mathcal{D}\models_s \phi\lor\psi, тогда и только тогда, когда \mathcal{D}\models_s \phiили \mathcal{D}\models_s \psiистинно,
  • \mathcal{D}\models_s \phi\to\psi, тогда и только тогда, когда \mathcal{D}\models_s \phiвлечет \mathcal{D}\models_s \psi,
  • \mathcal{D}\models_s \exists x\, \phi, тогда и только тогда, когда \mathcal{D}\models_{s'} \phiдля некоторой подстановки s', которая отличается от s только на переменной x,
  • \mathcal{D}\models_s \forall x\, \phi, тогда и только тогда, когда \mathcal{D}\models_{s'} \phiдля всех подстановок s', которые отличается от s только на переменной x.

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

7.4     Свойства и основные результаты

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

Логика первого порядка обладает свойством компактности: если некоторое множество формул не выполнимо, то невыполнимо также некоторое его конечное подмножество.

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

7.5     Использование

Логика первого порядка как формальная модель рассуждений

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

Возьмем рассуждение «Каждый человек смертен. Конфуций — человек. Следовательно, Конфуций смертен». Обозначим «x есть человек» через ЧЕЛОВЕК(x) и «x смертен» через СМЕРТЕН(x). Тогда утверждение «каждый человек смертен» может быть представлено формулой:  \forallx(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) утверждение «Конфуций — человек» формулой ЧЕЛОВЕК(Конфуций), и «Конфуций смертен» формулой СМЕРТЕН(Конфуций). Утверждение в целом теперь может быть записано формулой

( \forallx(ЧЕЛОВЕК(x) → СМЕРТЕН(x))  \andЧЕЛОВЕК(Конфуций) ) → СМЕРТЕН(Конфуций)

7.6     Литература

  • Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947
  • Клини С. К. Введение в метаматематику. М., 1957
  • Мендельсон Э. Введение в математическую логику. М., 1976
  • Новиков П. С. Элементы математической логики. М., 1959
  • Черч А. Введение в математическую логику, т. I. М. 1960
  • Логика высказываний
  • Логика второго порядка

8      Логика второго порядка

Логика второго порядка — расширяет логику первого порядка, позволяя проводить квантификацию общности и существования не только над атомами, но и над предикатами.

Логика второго порядка не упрощается к логике первого порядка.

8.1     Литература

 

 

Ссылка на этот материал: algebra_logiki.htm)

- - - ВЫ МОЖЕТЕ ОСТАВИТЬ ПЕРВЫЙ КОММЕНТАРИЙ! - - -


Введите логин:      Введите эл.адрес:

Введите пароль:    Ваш телефон:        

Введите Ваш комментарий:
Формулы:

(возможно использование BB-кодов для оформления комментария и кодов LaTeX для ввода формул)

Решите пример: 60 / "четыре" =

---Load files---
Сегодня - 20_08_2019
Время переоткрытия сайта 13 ч 59 м по Гр.
Календарь
на АВГУСТ месяц 2018 г.
Пн Вт Ср Чт Пт Сб Вс
      1; 2; 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31 1
(8 431)

---Load files---

---Load files---

© Все права защищены 2017-2019 При использовании материалов сайта ссылка на http://lowsofphisics.ru обязательна.

В НАЧАЛО
КОММЕНТ
В КОНЕЦ
U:5 V:6
Уникальных посетителей: 5 Просмотров: 6