вфцвфцввц. Математическая логика

• Название: Математическая логика
• Анкор: вфцвфцввц
• Дата: 05.12.2022
• Размер: 2.56 Mb.
• Имя файла: ML_i_TA_LEKTs.doc
• Тип: Задача; #828327
• страница: 1 из 7

МАТЕМАТИЧЕСКАЯ ЛОГИКА

Математическая логика, как и классическая логика, исследует процессы умозаключений и позволяет из истинности одних суждений делать выводы об истинности или ложности других, независимо от их конкретного содержания. Использование в логике математических методов (алгебраизация логики и построение логических исчислений) дало начало развитию новой области математики, называемой «Математической логикой». Основная задача математической логики – формализация знаний и рассуждений. Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, поэтому математическая логика, по существу, – наука о математике.

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

Вопросы, исследуемые математической логикой, могут рассматриваться как средствами семантической (смысловой) теории, в основе которой лежит понятие алгебры, так и формально-аксиоматической (синтаксической) теории, базирующейся на понятии логического исчисления. В данном курсе рассматриваются оба этих подхода, начав с алгебры высказываний, которая затем обобщается алгеброй предикатов, и обе они служат пониманию построения логических исчислений и их частных случаев: исчисления высказываний и исчисления предикатов.
Раздел I. АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

1. Высказывания и операции над ними. Формулы

Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно.

Например, утверждение "2 > 0" является высказыванием и оно истинно, а утверждение "2 < 0" - ложно, утверждение "x² + y² = z²" высказыванием не является, так как оно может быть, как истинным, так и ложным при различных значениях переменных x, y, z. Высказывание полностью определяется своим истинностным значением. Условимся, значение истинности высказывания обозначать 1, если высказывание истинно, и 0, если высказывание ложно, что в точности соответствует значениям переменных булевых функций.

Различают высказывания простые и сложные, высказывание называется простым, если никакая его часть не является высказыванием. Простые высказывания будем обозначать начальными заглавными буквами латинского алфавита A, B, C или A₁, A₂, . . .. Сложные высказывания характеризуются тем, что образованы из нескольких простых высказываний с помощью логических операций, т.е. являются формулами алгебры высказываний.

Напомним, что алгебраической структурой или алгеброй называется структура, образованная некоторым множеством вместе с введенными на нём операциями. Определим алгебру высказываний.

Обозначим через B= {0, 1} – множество высказываний. Определим операции на множестве B.

Отрицанием высказывания A называется высказывание, которое принимает значение истина, если A ложно, и наоборот. Отрицание обозначается (А) и является унарной операцией.

Пусть А и В - некоторые высказывания, введем бинарные операции над ними.

Конъюнкцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда истинны оба высказывания A и B. Обозначается конъюнкция - A B (АВ).

Дизъюнкцией высказываний A и B называется высказывание, которое принимает значение истина, если истинно хотя бы одно из высказываний A или B. Обозначается дизъюнкция - A B.

Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается АВ.

Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - АВ (АВ).

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

A	B	A	AB	AB	AB	AB
0 0 1 1	0 1 0 1	1 1 0 0	0 0 0 1	0 1 1 1	1 1 0 1	1 0 0 1

Пропозициональной (высказывательной) переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X₁, X₂, . . . , X_n.

Понятие формулы алгебры высказываний вводится по индукции. Формулами алгебры высказываний являются:

1) логические константы 0 и 1;

2) пропозициональные переменные;

3) если А и В – формулы, то каждое из выражений (А), (А)  (В), (А)  (В), (А)  (В), (А) (В) есть формула;

4) других формул, кроме построенных по пп. 1) - 3), нет.

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

Для формулы построенной по п. 3 формулы A и B называются подформулами. Число скобок в формуле можно сократить, Порядок выполнения операций в формуле определяется их приоритетом. Список логических операций в порядке убывания приоритета: . Изменение порядка выполнения операций, как и в алгебраических операциях, производится с помощью круглых скобок.

Пусть U– формула над высказывательными переменными X₁, X₂, . . . , X_n, обозначается U(X₁, X₂, . . . , X_n). Набор конкретных значений высказывательных переменных X₁, X₂, . . . , X_n называется интерпретацией формулы U и обозначается I(U).

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение 1 (существует интерпритация I(U), на которой формула истинна).

Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение 0 (существует интерпритация I(U), на которой формула ложна).

Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных (формула истинна на всех интерпретациях).

Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных (формула ложна на всех интерпретациях).

Формулы А и В называются эквивалентными (обозначается А  В), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В.

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

2. Следование, эквивалентность и преобразование формул

Введем на множестве M отношения следования и эквивалентности.

Формула B следует из формулы A (обозначается A B), если она истинна на всех наборах высказывательных переменных, на которых истинна формула A.

Теорема 2.1. Формула B следует из формулы A тогда и только тогда, когда тождественно истинна формула A B.

Доказательство. Пусть формула B следует из формулы A. Импликация A B ложна только на тех интерпретациях, на которых формула А истинна, а В ложна, что невозможно в силу условия.

Покажем обратное. Пусть A B – тождественно истинна, тогда если на некоторой интерпретации формула А истинна, то и формула В истинна на ней, что и означает A B.

Формула A эквивалентна формуле B (обозначается A  B), если они следуют друг из друга, то есть A B и B A. Легко показать, что это определение эквивалентно определению, введенному в п.1.

Теорема 2.2. Формула A эквивалентна формуле B тогда и только тогда, когда тождественно истинна формула AB.

Доказательство аналогично доказательству теоремы 2.1.

Приведем список основных тавтологий, выражающих свойства логических операций.

1. 
   Коммутативность:
   

X Y  Y X, X Y  YX.

2. Ассоциативность:

(X Y)Z  X (YZ), (XY)Z  X(YZ).

3. Идемпотентность:

XX  X, XX  X.

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

X(X Y)  X, X (XY)  X.

5. Взаимная дистрибутивность конъюнкции и дизъюнкции:

X (YZ)  (X Y)(X Z), X (YZ)  (XY)(XZ).

6. Свойства констант:

X0  Л, X1  X,

X0  X, X1  1.

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

, .

8. Инволютивность:

.

9. Закон противоречия:

 0.

10. Закон исключенного третьего:

 1.

Эквивалентность большинства из этих формул непосредственно следует из определения операций или проверяется построением таблиц истинности.

Пусть U – некоторая формула, в которую входит переменная X или подформула А, что обозначается U(, X,) или U(,А,). Пусть В – некоторая формула. Запись U(¼, X,¼){В//X} обозначает формулу, полученную из формулы U подстановкой формулы В вместо всех вхождений переменной X, а U(¼, А,¼){В/А} – формулу, полученную из формулы U подстановкой формулы В вместо некоторых (в частности, вместо одного) вхождений подформулы А.

Теорема 2.3 (правило подстановки). Если U(, X,) – тавтология и В – любая формула, то U(¼, X,¼){В//X} – тавтология.

Теорема 2.4 (правило замены). Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле U на B, эквивалентна U. Иными словами, если U(¼, А,¼) и A  B, то U  V= U(¼, А,¼){В/А}.

Например, так как AB  , то (AB)C  ( )C.

Следствие. Если UA и VB, то:

1) U V  A B;

2) U V  A B;

3) U V  A B;

4) (UV)  (AB);

5) U  A.

Теоремы 2.3, 2.4 и ее следствие позволяют преобразовывать формулы, упрощая их, и доказывать эквивалентность формул.

Примеры.

1. Докажем 1-й из законов поглощения X(X Y)  X.

.

При доказательстве использовано правило замены.

2. Упростить формулу .

Так как Xв силу подстановки в закон поглощения, тогда, используя правило замены получим

 .

Приведем еще несколько эквивалентностей, имеющих широкое применение.

11. 
    .
    
12. 
    .
    
13. 
    Законы склеивания
    

, .

Эквивалентность формул является отношением эквивалентности, поэтому множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [U].

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

Теорема 2.5. Каждый класс эквивалентности [U] может быть представлен приведенной формулой, т.е. для любой формулы U M существует приведенная формула V.

Доказательство теоремы проведём конструктивно, то есть определим порядок построения приведенной формулы.

1. 
   Удаляются операции импликация и эквиваленция по формулам 11, 12.
   
2. 
   Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания.
   
3. 
   Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10.
   

Таким образом, проверить эквивалентность формул, тождественную истинность и ложность формулы или упростить ее можно с помощью этого алгоритма.

Приведенная формула для данного класса эквивалентности не является единственной.

Задание. Упростить формулу .

Решение. 

   A.

Определение. Формула U^d называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкции на дизъюнкции и наоборот.

Теорема 2.6 (принцип двойственности). Пусть U( ) – приведенная формула, тогда

U^d( ) = U( ).

Доказательство. Число логических операций в формуле U называется рангом формулы и обозначается r(U). Проведем доказательство индукцией по k =r(U).

1⁰. k = 0. В этом случае U = X_i , следовательно, U^d = X_i    U ( ).

2 ⁰. Предположим, что теорема верна при k  m.

3 ⁰. Покажем, что она верна при k = m + 1.

Пусть U₁ и U₂ – подформулы U. Каждая из них образована посредством не более, чем m операций, и следовательно, для них теорема верна.

Возможны следующие случаи

а) U =  U₁;

б) U = U₁  U₂;

в) U = U₁  U₂.

Случай а) эквивалентен условию 1⁰ и при нем теорема верна. В случаях б) и в) заменим в каждой из U_i конъюнкцию на дизъюнкцию и наоборот. По определению двойственности будем иметь, соответственно, б): U^d = U  U и в): U^d = U  U .

В силу законов де Моргана и предположения индукции будем иметь в случае б):

U^d = U  U = (U₁ ( ))  (U₂ ( )) 

  (U₁ ( )  U₂ ( )) =  U( ).

В случае в) выкладки аналогичны. Теорема доказана.

Следствие. Если U – ТИ-формула, то U^d – ТЛ-формула.

Теорема 2.7. Если U  V, то U^d  V^d.

Доказательство. Если U  V, то (U)  (V). Значит, в силу теоремы 2.6, U^d(Х₁, …, Х_n) = U( ) и V^d(Х₁, …, Х_n) = V( ).

Отсюда: U^d = (U( ))  (V( )) = V^d. В силу транзитивности эквиваленции, получим U^d  V^d , что и требовалось доказать.

3. Использование законов логики в доказательстве

теорем и построении схем

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

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

А  В,

где А = “отношение R асимметрично”,

В = “отношение R антирефлексивно”.

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

А  В (А  В, В  А),

где А = “граф G – связный”,

В = “вершина v достижима из всех вершин”.

Согласно теоремам 2.1 и 2.2, следование А  В имеет место тогда и только тогда, когда импликация А  В является ТИ-формулой, а двойное следование А  В выполняется, когда ТИ-формулой является эквиваленция А  В. Таким образом, для доказательства какой-либо теоремы надо доказать ТИ соответствующей импликации или эквиваленции. Рассмотрим основные приемы таких доказательств, использующие законы математической логики.

Определение 1. Если АВ является истинным высказыванием, то истинность А является достаточным условием истинности В, а истинность В – необходимым условием истинности А.

Определение 2. Теоремы, записанные в виде импликаций АВ и ВА называются взаимно-обратными. Если верны обе импликации, то истинность А является необходимым и достаточным условием истинности В, и наоборот.

Определение 3. Теоремы, записанные в виде импликаций АВ и называются взаимно-противоположными.

Предположим, что утверждение А истинно и докажем, что в этом случае В тоже истинно. Так доказывается теорема вида А  В. Однако такая схема доказательства “в лоб” не всегда удобна. Для доказательства истинности импликаций и эквиваленций часто используют свойства эквивалентности формул.

Известно, что

А  В  В     (А  ) .

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

Например, А = “отношение R асимметрично”, В = “отношение R антирефлексивно”. Тогда доказательство по схеме выглядит так: R рефлексивно, т.е. (х, х)  R, значит, (х, х)  R^{– 1} , т.е. (х, х)  R  R^{– 1}  . Это означает, что R не асимметрично.

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

Например, предположим, что R асимметрично и рефлексивно. В силу асимметричности неверно одно из следующих соотношений: (х, у)  R и (у, х)  R. Положим х = у. Тогда, включение (х, х)  R неверно, т.е. утверждение – ложно, значит и (А  ) – ложно.

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

Каждой схеме ставится в соответствие формула алгебры высказываний, и каждая формула реализуется с помощью некоторой схемы. Покажем, как уста­новить такое соответствие. Каждому переключателю P ставится в соответствие высказывательная переменная P, которая истинна тогда и только тогда, когда переключатель P замкнут. Схеме с последовательным соединением переключа­телей P и Q соответствует формула, являющаяся конъюнкцией высказаватель­ных переменных, соответствующих этим переключателям, . Схеме с параллель­ным соединением переключателей P и Q соответствует формула, являющаяся дизъюнкцией высказавательных переменных, соответствующих этим переклю­чателям, . Два переключателя P и могут быть связаны так, что когда P замкнут, то разомкнут. Тогда переключателю ставится в соответствие переменная , являющаяся отрицанием P.

Задание. Упростить схему




Решение. Запишем формулу, соответствующую схеме, по приведенным выше правилам

U = .