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

Вид материала

Документы

Содержание Парадигмы формальной логики. Предмет, цель, задачи и содержание читаемого курса лекций. Место читаемого курса о законах и формах правильного мышления. Концептуальный базис математической логики. Построение математической логики. Язык классической логики высказываний Семантика Я.Л.В. Классическая логика высказываний. Язык классической логики предикатов (я.л.п.). Синтаксис языка Л.П. Алфавит Я.Л.П. Индуктивное определение Примеры перевода простых высказываний естественного языка и их отрицаний на язык логики предикатов. Семантика ялп. Классическая логика предикатов. Алгебра логики предикатов. Выражение отношений посредством многоместных предикатов Квантификация предикатов. Эквивалентные преобразования кванторных формул. 2) Законы коммутативности одноименных кванторов. ... Полное содержание

Подобный материал:

• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Программы кандидатского экзамена по специальности 01. 01. 06 "Математическая логика,, 50.44kb.
• Рабочая учебная программа по дисциплине математическая логика, 72.41kb.
• Рабочей программы учебной дисциплины дв2 Математическая логика и теория алгоритмов, 50.1kb.
• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Н. В. Папуловская Математическая логика Методическое пособие, 786.38kb.
• Уакиев Валериан Савирович рекомендуемая литература, 334.04kb.
• Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
• Логика компьютера, 210.22kb.
• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.

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

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

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


Логика высказываний, как и логика предикатов, имеет два аспекта: семантический, когда она является содержательной теорией логических отношений между суждениями; синтаксический, когда логика является методом дедуктивной формализацией содержательных теорий.

Замечание.

1. Согласно П.Г.Порецкого математическая логика есть логика по предмету, математика по методу, а согласно Г.Фреге математическая логика изучает логику математики путем ее дедуктивной формализации.
   
2. Математическая логика есть современный этап в развитии формальной логики – науки о построении правильных заключений (доказательств, опровержений) чисто формальным путем, когда исходят из вида (логической формы) посылок, а не их содержания.
   
3. Логика, в отличие от математики (изучающей количественные отношения и пространственные формы) изучает не количественные отношения между объектами.
   
4. Математическая логика пришла на смену традиционной(описательной) формальной логике во 2-ой половине 19в.-начале 20 века.
   
5. Познание объясняется следующим деревом:
   

Познание

(процесс гомоморфного отображения действительности)

дедукция

индукция

аналогия

Логические приемы оперирования с формами познания

Приемы интеллектуального (рационального, языкового) познания

Способы познания

Чувственные формы познания


Рациональные формы познания

ощущение

восприятие

представление

понятия

высказывание

теории

Логические приемы образования форм познания

6. Основными объектами математической логики являются: высказывания и логические процедуры. Поскольку все научные знания, процессы управления и др. формулируются, как последовательность утвердительных повествовательных предложений (т.е. высказываний субъектно-предикатной структуры).
   
7. Науки, предложения которых преимущественно получаются как следствия некоторых общих принципов, постулатов, аксиом, принято называть дедуктивными, а аксиоматический метод, посредством которого выводы этих частных предложений, часто называют аксиоматико-дедуктивными.
   
8. Основная задача логики – отделение правильных схем рассуждения (умозаключения, доказательств – мыслительного процесса, в ходе которого из одного или нескольких суждений, называемых……., выводится новое суждение, называемое заключением или следствием) от неправильных и систематизации первых.
   

ПАРАДИГМЫ ФОРМАЛЬНОЙ ЛОГИКИ.

1. Правильность рассуждения (умозаключения, вывода, доказательства) зависит только от его формы и не зависит то его конкретного содержания.
   
2. Истинность и правильность мышления суть различных объектов:
   
   • истинность характеризует рассуждение в его отношении к действительности;
     
   • правильность характеризует рассуждение в его отношении к законам и правилам логики.
     

Пояснение. Различие между истинностью и правильностью отчетливо видно в тех случаях, когда формально правильное рассуждение приводит к логическому высказыванию.

Пример. Все металлы – твердые тела.

Ртуть – не твердое тело.

Ртуть - не металл.

Это правильное умозаключение логично (из-за логики первой посылки).


ПРЕДМЕТ, ЦЕЛЬ, ЗАДАЧИ И СОДЕРЖАНИЕ ЧИТАЕМОГО КУРСА ЛЕКЦИЙ.

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

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

Задачи дисциплины:

• освоение предметных языков логики высказываний и логики предикатов;
  
• приобретение навыков использования дедуктивных методов вывода заключений из посылок;
  
• умение работать с различными моделями формального уточнения понятия “алгоритм”.
  

Содержание читаемого курса представим следующим деревом:


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

F.S=

Прикладные исчисления

_п=< L(_в), D(_в)>

_B=< L(_B), D(_B)>

Классическое _п

Классическое _В

неклассическое _п

неклассическое _В

Многозначное _В

Логическое исчисление


А_B

А_П

А=
Метатеория логических исчислений


Здесь:

А=
F.S= - формальная система (т.е. построение математической логики, как теории, является чисто синтаксическим объектом);

 - исчисление ( _в - исчисление высказываний; _п - исчисление предикатов);

L – язык (L(_в) – язык исчисления высказываний, L(_п) – язык исчисления предикатов), т.е. множество синтаксически правильно построенных выражений(формы F).

D – дедуктивные средства (D(_в) – дедуктивные средства исчисления высказываний, D(_п) – дедуктивные средства исчисления предикатов);

А_B = < B, B²  - алгебра логики высказываний;

А_B = < Р_(Х1, …, _Хn),  ,B²,  - алгебра логики предикатов.

Примечание. В том случае, если между морфологическими элементами формальной системы F.S. и элементами содержательной системы А существует функциональная биекция, то все исходные

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


МЕСТО ЧИТАЕМОГО КУРСА О ЗАКОНАХ И ФОРМАХ ПРАВИЛЬНОГО МЫШЛЕНИЯ.

Логика


Диалектическая логика

Дедуктивные (достоверные) логики

Металогика (методология дедуктивных наук)

Формальная логика (наука о законах выводного знания)

Индуктивные (правдоподобные) логики

Математическая (теоретическая) логика

Нечеткая логика

Традиционная (описательная)

логика


Античная логика

Четкая логика

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

Конечнозначные

логика

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

Бесконечнозначные логика

Счетнозначная логика

Вероятностная логика

Функциональные системы

Формальные

системы

Алгебра логики предикатов

Алгебра логики высказываний

метатеории

исчисления

Пояснения к этому дереву сделаем следующие:

1. Предмет логики (по Аристотелю – средство обоснования истины) отличается от предмета всех других наук тем, что она(логика) исследует не закономерности объективного мира (природы, общества), чем занимаются естественные науки (физика, химия, биология) и общественно-политические науки (история, социология), а законы и формы логического мышления, оставляя в стороне описание фактического процесса протекания мышления по законам причинного следования (это предмет психологии).
   

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


Мышление человека

Мышление как объект изучения.

Науки, изучающие мышление

логика

Мышление как познание объективного мира

Науки, изучающие объективный мир

Естественные науки

Общественно-политические науки

Философия, физиология, психология, кибернетика.

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

2. Дедукция – переход от общего к частному по правилам логического вывода, позволяющие получить из истинных посылок(известных знаний) истинное заключение (новое знание, т.е. выводное знание).
   
3. Индукция – переход от частного к общему. В отличии от дедуктивных рассуждений(построений) индукция не гарантирует истинного заключения при истинности посылок. Принято дедуктивную логику называть достоверной, а индуктивную логику – правдоподобной (проблемотичой). Деление выводов(умозаключений в традиционной логике) в современной логике на правильные и неправильные означает различие отношения логического следования на два вида – дедуктивные и индуктивные.
   
4. Формальная логика – наука о законах выводного знания, т.е. знания, полученного из раннее установленных и проверенных истин (без обращения в каждом конкретном случае к опыту) только с помощью законов и правил логического мышления. В соответствии с основным принципом логики правильность рассуждения (умозаключения, доказательства, вывода) зависит только от его формы и не зависит от его конкретного содержания.
   
5. Традиционная (описательная) логика, как совокупность………….., изучает общечеловеческие законы правильного построения и сочетания мыслей в рассуждениях, общечеловеческие формы мыслей (понятия, суждения) и формы умозаключений, а также средства мысли (определения, как отношения между понятиями; принципы образования понятий; суждений, умозаключений),необходимых для рационального (языкового) познания в любой области человеческой деятельности.
   
6. Математическая логика (как современный этап развития формальной логики) изучает логику содержательных теорий (т.е. множество взаимосвязанных понятий и высказываний, замкнутое относительно логической выводимости) средствами математики, а логику самой математики – с помощью различного рода исчислений.
   

Замечание. Отличие математики от логики поясним вопросами, ответы на которые они ищут.


Вопросы математики

Сколько?

Как далеко?

Как долго?

(т.е. вопросы о количественных отношениях)

Вопросы логики

Что это значит?

Есть ли противоречие в этом суждении?

Каковы основания этого доказательства?

(т.е. вопросы о неколичественных отношениях)

7. Нечеткая логика – логика, истинностные значения высказывания которой интерпретируются нечетким подмножеством заданного множества значений.
   
8. Четкая логика – логика, в которой для интерпретации высказываний используется множество истинностных значений М. Говорят, что логика называется:
   

• классической (двузначной), если |M|=2, т.е. М={0,1} или М={U,};
  
• неклассической (многозначной), если |M|>2;
  
• бесконечнозначной, если |M|=N (это т. н. счетнозначные логики) или |M|=D (это т.н. логики);
  
• вероятностной, если истинностные значения М представляются вероятностями; степенями правдоподобия высказываний);
  
• темпоральной(временной), если элементы М зависят от времени;
  
• модальной, если алфавит ее языка включает связки, интерпретируемые как “возможно, что…”
  

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

КОНЦЕПТУАЛЬНЫЙ БАЗИС МАТЕМАТИЧЕСКОЙ ЛОГИКИ.


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


Основные понятия математической логики

высказывания

Простые высказывания

Сложные высказывания

метавысказывания

термы

Логические переменные

Предметные переменные

Пропозициональные переменные

Лингвистические переменные

Предикатные переменные

Метапеременные

Субъекты

Логические операторы

Истинностные значения

метатермbys

Логические функции

Однородные логические функции

Неоднородные логические функции (предикаты)

Метафункции

Логические формулы

Предикатные формулы

Пропозициональные формулы

метаформулы

Здесь:
А. Высказывание – абстракция осмысленного повествовательного предложения естественного языка, для которого имеет смысл говорить о его истинности или ложности (это пояснение, а не определение, понятие “высказывание” в классической логике).

• Простые высказывания.
  

Примеры:

1. Вычислительная система есть программно-аппаратный комплекс.
   
2. 57=35
   

Эти два предложения являются простыми (атомарными, элементарными) истинными высказываниями.

Примеры:

3. 3
   
4. Волк есть дикая кошка.
   

Эти два простых высказывания являются ложными.

5) Денис скоро будет космонафтом.(не высказывание,т.к. будущее время)

Предостережения:

• предложение “Всякий вечный двигатель работает без бензина ” и “ Земля вращается быстро ” не являются истинными, но в тоже время не являются и ложными. Поэтому эти предложения не являются высказываниями (очевидно, что первое предложение является бессмысленным, а второе – неопределенно-истинно);
  
• предложение Х+7=9 не является высказыванием, а есть высказывательная форма (при указании конкретного значения Х имеем высказывание).
  

Следует отметить, что всякое простое,бескванторное, категоричное высказывание имеет субъектно-предикатную структуру (т.е. логическую форму, способ содержательных частей) вида a  P ( или сокращенно P_(a)), где a – субъект (субъект указывает на тот объект, о котором идет речь в высказывании);

P – предикатный терм (предикатный терм, иначе, логическое сказуемое, указывает на свойство субъекта);

 - оператор предикации;

• Сложные высказывания.
  

Примеры:

1. Волга – самая короткая река России и в ней живут киты;
   
2. 3+7=9 аналогично 7+3=2
   

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

P_1(a) P_2(a) или (a  P₁)  (a  P₂),


P_3(b) ~ P_4(b) или (b  P₃) ~ (b P₄),

Где: a, b – субъекты (соответственно: Волга и сумма чисел);

P_1, P_2, P_3, P₄ - предикатные символы (соответственно: самая короткая река; река, в которой живут киты; равно 9; равно 2);

 - логические связки (обозначающие соответственно “и” и “аналогично”),позволяющие строить из простых высказываний сложные.

• Метавысказывания – это высказывание, субъект которого указывает на другое высказывание.
  

Пример. Пусть имеем высказывание P_(a) , тогда высказывание “ P_(a) - ложно ” о высказывании P_(a) есть метавысказывание. Очевидно, на основе высказывания P_(a) можно построить неограниченное количество метавысказываний различной степени сложности. Так, например, метевысказыванием будет “высказывание “ P_(a) - ложно” - истинно”. Поскольку в математической логике сложное высказывания представляют замкнутой формулой, то высказывание о ее доказуемости (недоказуемости, выполнимости) является метавысказыванием. При этом в целях упрощения записи метавысказываний используются оператор логического

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

___

“формула” P_(a) P_(a)” – тавтология” записывается символически |= (P_(a) P_(a)), а метавысказывание “ формула“ P_(a) P_(a) ” – логически доказуема” записывается так |(P_(a) P_(a)).

Б. Терм – языковое выражение для обозначения некоторых эмпирических и абстрактных объектов. Термы строятся по определенным синтаксическим правилам в конкретном языке логики. Обычно термы задают с помощью логических переменных и терминов.

1. Логическая переменная – символ языка, обозначающий произвольный объект из некоторого фиксированного множества объектов. В читаемом курсе логическими переменными являются:
   

• предметная переменная – переменная, выражающая предмет(субъект, индивидный объект);
  

Примеры:
1) Х – студент группы “C”, т.е. P_(x) , где

Х – субъект ( на множестве студентов группы “C”; P - является студентом группы “C”

2) Х+3=5 т.е. P_(x) , где х – числовая переменная(т.е. место для подстановки цифр, обозначающих конкретное число); P – является слагаемым уравнения 1-го порядка.

Р(2)-истинное высказывание.

3) Х сын Y, P_(x,y) , где x,y - прямые родственники, P - быть сыном.

Места,которые надо обозначить из множества родственников:

• пропозициональная переменная – переменная, значениями которой являются высказывания;
  
• лингвистическая переменная (в нечеткой логике) – переменная, значениями которой являются субъективные словесные оценки;
  
• предикатная переменная - переменная, значениями которой являются предикаты;
  
• метапеременная – переменная, вместо которой допускается подстановка других переменных определенного вида.
  

2. Термин – символ имени (именной формы) конкретного объекта. Различают термины:
   

• индивидные (предметные, субъектные) постоянные (константы);
  
• логические операторы (составляющие три подмножества – логические связи, такие как, кванторы, такие, как ; символы метавысказываний, а именно |=, |
  
• предикатные термины (двухместные отношения , ;
  
• истинностное значение – абстрактный объект, выступающий в качестве характеристического свойства высказывания (в классической логике ={U, }, а в неклассической - || >2; здесь  - множество истинностных значений для высказываний).
  
• Метатермин – термин для обозначения множества терминов.
  

В. Логическая функция – функциональное соответствие на множестве кортежей длины n>0, принимающее значение в множестве истинностных значений, т.е.

S_f : M₁ M₂ …  M_k

Различают однородные (пропозициональные) и неоднородные (предикатные) логические функции, т.е.

1. если M₁= M₂= … = M_n= , то ⁿ - однородная логическая функция (в частности, если || =2, то пишут f:{0,1}ⁿ{0,1}, или f: ВⁿВ и называют функциями алгебры логики).
   
2. Мⁿ - неоднородная логическая функция (в частности, Мⁿ{0,1} – двузначный n-местный предикат)
   
3. Метафункция - метаформулы.
   

Г. Логическая формула – языковое представление суперпозиции логических функций. В читаемом курсе будем различать формулы:

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

Примечание.

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

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.


Математическая логика является теорией (т.е. целостной системой абстрактных объектов, отражающей основные закономерности логического мышления) в том плане, что ее основными структурными компонентами являются:

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

В том случае, когда абстрактные объекты теории отображаются с помощью формального или формализованного языка L= (соответственно, L₁= , L₂=1, S₂> , где А – алфавит символов, S₁ – синтаксические правила построения языковых выражений FA^* , S₂ - семантические правила ) и явным образом определены постулаты D (т.е. аксиомы A_x  F A^* и дедуктивные средства P  Fⁿ⁺¹), то говорят о построении теории как формальной системы F.S. = = x, P> x, P>. Примером так построенной теории в читаемом курсе будут рассмотрены исчисления высказываний и предикатов (это т.н. логические исчисления).

Другим подходом к построению математической логике является - содержательный, т.е. неформальный. В этом случае аксиомы и дедуктивные средства явным образом не определяются (т.е. постулаты в таком построении теории используются интуитивно). Примером содержательно построенной математической логикой является алгебра логики – алгебра высказываний А₁=<{U, }, , , > и алгебра предикатов А₂=< F, , {U, }²{U, },  > (где F – множество предикатных формул,  - символ отрицания, {U, }²{U, } – бинарные логические связки, - квантор всеобщности,  - квантор существования).

Замечания.

1. Содержательная надстройка современных теорий строится на основе точно заданного концептуального базиса нечетко определенных дедуктивных средств.
   
2. Необходимым, но недостаточным условием научной состоятельности теории является ее внутренняя непротиворечивость.
   
3. Логические исчисления являются важнейшей разновидностью формальных систем F.S. От других формальных систем ( например, интегрального и дифференциального исчисления) логические исчисления отличаются чисто логическим пониманием правильно построенных языковых выражений FA^* и правил вывода P : (F₁, F₂,…, F_n, F_n+1)  Fⁿ⁺¹
   
4. На основе логических исчислений строятся ( путем присоединения некоторых дополнительных аксиом) прикладные исчисления.
   
5. Для всякого логического исчисления важное значение имеет вопрос о его непротиворечивости, независимости, полноте, разрешимости.
   
6. Говорят, что всякая интерпретированная формальная система (т.е. когда L=1, S₂> ) представляет собой формализованный язык, в котором заданы S₁ - правила синтаксиса и S₂ - правила семантики (интерпретации). Именно в этом плане изучаемые в курсе исчисления высказываний _в и предикатов _п являются интерпретированными логическими формальными системами (или логическими языками). Примером интерпретированных прикладных логико-математических F.S. (или т.н. логико-математических языков) являются различные аксиоматико-дедуктивные теории множеств.
   
7. F.S. есть порождающая процедура (т.е. аксиоматико-дедуктивный способ индуктивного порождения элементов множества из исходных объектов, рассматриваемых как аксиомы, или разрешаемое подмножество A_x  F), а интерпретация, как метод, является распознающей процедурой (т.е. способом распознавания принадлежности объекта заданному множеству).
   
8. Правила вывода P формальной системы < L, D > есть конечное множество вычисляемых (разрешающих) отношений на множестве языковых выражений FA^*.
   

Для лучшего усвоения формального построения теории приведем примеры формальных систем F.S., несвязанных с логическими интерпретациями.

Пример 1. Пусть F.S.= x, P> есть описание (интерпретация) игры в шахматы, т.е. F.S. описывает множество допустимых шахматных позиций. В этом случае алфавит А состоит из 64 клеток доски, занятые фигурами и свободные; синтаксические правила S порождают множество допустимых позиций F; аксиомой (единственной) A_x является исходная шахматная позиция; правилами P являются правила, определяющие следующие ходы (чередование ходов белых и черных фигур, правила взятия фигур, рокировки, допустимого хода фигур на свободные клетки) и заключительные позиции – ничейные, матовые.

Пример 2. Фраза русского языка описывается F.S., алфавит которой А – алфавит русского языка, S – грамматические правила построения слов русского языка F, аксиомы A_{x –} слова фразы, а правила вывода P , т.е. правила построения фразы из слов – правила синтеза фраз в грамматике русского языка.

Пример 3. Формальная грамматика есть формальная система, описывающая синтаксис искусственного языка. В этом случае алфавит А есть объединение двух непересекающих подмножеств символов терминального Т и вспомогательного V словарей (т.е. А=ТV), а формулами – цепочки из этих символов (т.е. FТV^*). Единственная аксиома  в этой формальной системе является элементом вспомогательного словаря V (т.е. V), правило вывода позволяет получать цепочки в терминальном алфавите ( эти цепочки являются словами искусственного языка – множества, порождаемого формальной грамматикой) и имеют вид h, где , hТV^*. Так, формальная грамматика (система)  порождает (описывает) множество (язык) нечетных чисел в унарном представлении, т.е. множество цепочек вида , ,…, ^2n-1,… (здесь nN ).

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

Так, индуктивное определение двухполюсной системы вида

б


а

с

d

k

Может быть следующим:

1. объект ха, б, с, д,…, к является схемой, полюсы которой совпадают с полюсами объекта (язык построения объекта L( может быть описано, например, какой-нибудь формальной грамматикой)
   
2. если С_i и С_j – схемы, то
   

C_i

C_i

C_j

C_j


также схемы (это т.н. правила последовательного p₁ и параллельного p₂ соединения схем в схему)

3. других схем нет.
   

В этом случае F.S.= < L (),а, б, с, д,…, к, p₁, p₂ >

ЯЗЫК КЛАССИЧЕСКОЙ ЛОГИКИ ВЫСКАЗЫВАНИЙ L_В = <A_В, F_В>.

А. Синтаксис языка Л.В,

Перечисленные множества исходных символов алфавита A_В и правил образования языковых выражений, составляет синтаксис языка логики высказываний (Я.Л.В.).

1. Алфавит Я.Л.В.
   

A_{В =} ₁₂₃; _i_j = , ij; ₁={p, q, x, y,…,p₁, q₁, x₁, y₁,… p₂, q₂, x₂, y₂,… } – множество дескриптивных (нелогических) символов, называемых пропозициональными термами (переменными). Эти символы используются как параметры (буквы) простых высказываний (при выявлении логических форм контекстов естественного языка). ₂={} – множество логических символов (констант), называемых пропозициональными связками. Эти символы являются терминами, обозначающими логические отношения и образующие функционально-полную систему (т.е. из них можно выразить любую логическую функцию).

₃={(,) } - множество разделительных (технических) знаков

Примечание.

1. ₁₂ – есть множество значащих символов.
   
2. В языке логики высказываний логические связки получают единую и постоянную интерпретацию ( - не;  - или;  - и;  - если…то), а пропозициональные переменные в составе формул и формулы могут получать различные интерпретации от случая к случаю. Существование такой интерпретации определяет семантику языка.
   

2. Языковые выражения Л.В.
   

Языковыми выражениями в логике высказываний являются формулы, называемые пропозициональными формулами. Язык формул с переменными x,y,z порождается формальной грамматикой = <Т, V, , P >, где Т= x,y,z,  ; V ={}, P =хy, z

Замечание.

1. В алгебре логике формулы Я.Л.В. являются аналитическим способом представления (реализации, задания) пропозициональной функции {U, }²{U, }, а в логике высказываний – логическими формами высказываний.
   
2. Принять следующие сложные высказывания (задаваемые их логическими формами, т.е. формулами Я.Л.В.) (ху), (ху), х  у, х называть соответственно дизъюнктивным, конъюнктивным, импликативным и отрицанием, связки   - дизъюнкцией, конъюнкцией, импликацией, отрицанием.
   

Б. Семантика Я.Л.В.

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

Пропозициональные переменные	Пропозициональные формулы
x	y	х	(ху)	(ху)	х  у
		U			U
	U	U	U		U
U			U		
U	U		U	U	U

Использование таких таблиц позволяет вычислить истинностное значение любой формулы Я.Л.В.

Пример. Вычислить истинностное значение высказывания вида:

((ху) х), если х=, у= U. Имеем

Переменные	Подформулы		Формулы
х	у	(ху)	х	(ху) х
	U	U	U	U

Т.е. при заданной интерпретации простых высказываний сложное высказывание истинно. Часто результат интерпретации формулы записывают так:

|((ху) х)| = И при х=, у= U.

Примечание. Для упрощения записи логических форм

1. вводят старшинство связок, а “лишние” скобки опускают;
   
2. используют производные связки (связки  в таком случае называют основными).
   

Пояснения:

1) о соглашениях по сокращению записи формул над множеством логических связок:

• внешние скобки формул опускаются
  

_

• формуле х записывается в виде х ;
  
• формуле (ху) записывается в виде ху ( т.е. скобки и символ операции опускаются);
  
• приоритет в последовательности применения связок возрастает в следующем порядке:  ( т.е. унарная связка  сильнее любой бинарной операции; связка  - самая сильная бинарная операция).
  

Эти соглашения позволяют записать формулу:

_ _

((((х) у)  z) ( х (y)  z)) записать в более компактном виде ( ху)zxyz

2) Производные связки для сокращения записи логических выражений

• оператор “эквиваленция”  (интерпретируется как союз естественного языка “тогда и только тогда”) позволяет формулу (ху)  (ух) записать в виде ху, т.е. (ху)(ух)= ху (часто  называют оператором эквивалентности)
  
• строгая дизъюнкция  (интерпретируется как союз “либо…либо” ) позволяет формулу (х y)  (х  у) записать в виде х  у (часто вместо символа  используется символ , т.е. пишут ху);
  

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

х – треугольник прямоугольный,y - треугольник остроугольный, z - треугольник тупоугольный. Терминам “не” соответствует связка , “тогда и только тогда” - , “либо…либо” - . Логическая форма исходного высказывания х  (у z), в Я.Л.В. имеет вид:

_ _ _ _ _ _ _ _

(х  (у z))( (у z) х) = (хyz  yz)(yz  yzx)

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

Пример. Сложное высказывание “Земля по форме есть эллипсоид Красовского тогда и только тогда, если неверно, что Земля не есть по форме эллипсоид Красовского”. Это высказывание (его логическая форма ₁ ₂ ) есть тавтология ₁ ₂, где ₁ – первое простое высказывание, а ₂ – второе простое высказывание исходного сложного высказывания.

КЛАССИЧЕСКАЯ ЛОГИКА ВЫСКАЗЫВАНИЙ.

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

• выделяет среди класса формул множество своих законов;
  
• устанавливает логические отношения между формулами.
  

В этом плане формально логику высказываний понимают как определенное на множестве формул языка логики высказываний отношение логического следования |= и законов, т.е. < F,|= >, с привлечением таблиц истинности.

а) Законы классической логики высказываний.

Определение. Формула, которая при любых распределениях истинностных значений ее параметров принимает значение “истина”, называется общезначимой.

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

Для метавысказывания “А есть логический закон” принять обозначение |=A (здесь А – метаформула). Так, принцип исключенного третьего выражается метавысказыванием |= ( , говорящим о том, что общезначимой является пропозициональная формула ( , а принцип противоречивости выражает метавысказывание |=(  , говорящее о том, что общезначимой является формула (  , (где  - пропозициональная переменная, |= - оператор логического следования). При подстановке вместо  любых конкретных высказываний (как истинных, так и ложных) из формул (  и  (  получаются только истинные высказывания.

Замечание.

1. Факт общезначимости пропозициональной формулы устанавливается с привлечением таблицы истинности (пассивный метод) или эквивалентным преобразованием (активный метод).
   
2. Каждый закон логики имеет бесконечное множество вариантов формульного представления. Так принцип исключенного третьего может быть записан следующими аналитическими выражениями:
   

|=x x; |=(ху) (ху); |=((xz) (yp)  ((хz)(yp));

3. Тождественно-ложная формула (т.е. формула, имеющая значение “ложь” на всех значениях истинности ее переменных) являются отрицанием закона логики.
   

б) Отношения логического следования и логической эквивалентности.

1. Из множества формул T логики следует формула В (символическая запись T |=B, или R(F₁, F₂,…, F_n , F_n+1=B), где T ={ F_1, F₂,…, F_n }) в логической теории, если и только если в теории не существует интерпретации нелогических символов, входящих в T и В, при которой каждая формула из T принимает значения “истина”, а формула В - значение “ложь”. Иначе, логическое следование ₁₂ - отношение между пропозициональными формулами ₁ и ₂ такое, что ₁ ₂. В противном случае, т.е. когда формулы T истинны, а В – ложны, то В не следует из T (символически запись T |В). В логике высказываний эффективной процедурой (алгоритмом) выявления отношения логического следования между конечным множеством формул T и формулой В является таблица истинности.
   

Пример 1. Проверить правильность умозаключения “Если тело движеися равномерно и прямолинейно, то на него не действуют силы. Тело движется равномерно, но не прямолинейно. Следовательно, на тело действуют силы”. Логическая форма заданного умозаключения имеет вид:

(
посылки T
(рq) z)

(
заключение
рq)

z


здесь р – “тело движется равномерно”

q – “тело движется прямолинейно”

z – “на тело действуют силы”

Таблица истинности умозаключения имеет вид:

Пропозициональные переменные			посылки					заключение
p	q	z	((рq) z)			(рq)		z
U U U U    	U U   U U  	U  U  U  U 	 U U U U U U U				  U U   U U	U  U  U  U 

В четвертой строке этой таблицы посылки истинны, а заключение – ложно. Поэтому из ((рq) z), (рq) не следует логически z и, следовательно, умозаключение является неправильным.

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

• все посылки T истинны, а само умозаключение не правильно;
  
• умозаключение правильно, но в нем есть ложная (ложные) посылки;
  
• умозаключение не правильно и в нем есть ложная посылка. В этом плане следует отметить, что если к истинным посылкам T применяется правильное умозаключение, то с логической неотвратимостью будет получено истинное заключение В, т.е. T |=В.
  

Пример 2. Согласно легенде обоснования сожжения книг Александрийской библиотеки :

- если ваши книги согласны с Кораном (р), то они излишни (q), (рq)

- если же ваши книги не согласны с Кораном (р), то они вредны (z), (рz)

- но вредные (z) или излишние(q) книги следует уничтожать(у), (qz) y

Поэтому ваши книги следует уничтожать.

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


р
посылки
q

рz

(
заключение
qz) y

y


Построив таблицу истинности, заключаем, что (рq), (рz), ((qz) y) |= y.

Аналитически этот результат можно получить, если учесть, что согласно теореме дедукции:

|=( F₁…( F_n В)…)  F_1, F₂,…, F_n|=В, в нашем случае: надо показать, что

|=(( рq) ((рz) (((qz) y))), т.е. ((рq) ((рz) (((qz) y) y)))=


Пример 3Рассуждение “Если на данное движущееся тело не действуют никакие силы или равнодействующая всех действующих сил равна нулю, то оно движется равномерно. Данное тело движется неравномерно, следовательно, равнодействующая всех действующих сил не равна нулю”. Это умозаключение, логическая форма которого

((рq) r)

r

q


правильно, т.е. ((рq) z), r |=q

действительно:

_ _ _ _ _ _ _ _ _ _ _ _ _ _

(((рq) r) (rq))  (p qr) (rq)  (p r  q r  r  q)  (p r  q r  r  q rq r )  (p r  r 

_

 r )=u

II. Формулы А и С логически эквивалентны (логически равнозначны), если и только если из А логически следует С и из С логически следует А, т.е. имеет место двустороннее логическое следование:

A|=C и C|=A

Из этого определения вытекает, что в каждой строке совместной таблицы истинности обе логически эквивалентные формулы принимают одинаковые значения, что можно записать следующим образом АС(АС)(СА). Если АС и СА тождественно истинны, то АС есть закон, т.е. |= АС.

Примечание. Таблично алгебраическим вариантом логики высказываний является алгебра логика, имеющая большое прикладное значение в синтезе комбинационных автоматов. Однако, если в логике высказываний формула рассматривается как логическая форма высказывания, то в алгебре логики формула является аналитическим способом представления логической функции f:{0,1}ⁿ {0,1}, где {0,1} заменяют истинностные значения {, И} логики высказываний.

ЯЗЫК КЛАССИЧЕСКОЙ ЛОГИКИ ПРЕДИКАТОВ (Я.Л.П.).

Язык логики предикатов n,, F_n > является расширением рассмотренного выше языка логики высказываний.

А. Синтаксис языка Л.П.

Синтаксис Я.Л.П. обусловлен алфавитом A_n и правилами образования из символов A_n языковых выражений термов  и формул F_n

1. Алфавит Я.Л.П. A_n
   

Множество символов A_n рассматриваемого формализованного языка состоит из трех подмножеств – дескриптивных терминов ₁, логических операторов ₂ и вспомогательных символов _3.

а)Дескриптивные термины _1. Дескриптивными (нелогическими) терминами редметные (индивидные) константы {a,b,c,d,…,a₁,b₁,c₁,d₁,…,a₂,…}, n-местные предметно-функциональные константы {f,g,h,…,f₁,g₁,h₁,…,f₂,…}, m-местные предикатные константы {P,Q,R,S,…,P₁,Q₁,R₁,S₁,…,P₂,…}, и предметные (индивидные) переменные {x,y,z,…,x₁,y₁,z₁,…,x₂,…} (это пропозициональные переменные)

Пояснение.

1. При переводе выражений естественного языка на Я.Л.П. объекты заменяются индивидными константами;
   
2. n-местные предметно-функциональные константы (n1) соответствуют предметным функторам естественного языка, таким как “ сложение”, “вычитание”, извлечение корня, дифференцирование, расстояние от…до…(вообще, n-местные предметный функтор обозначает n-местную предметную функцию).
   

3) m- местные предикаторные константы ( m  1) соответствуют предикатам естественного языка, т.е. знакам свойств ( например, горячий, электропроводный, зеленый) и отношений ( например, южнее, больше, старше). При этом свойства в ЯЛП являются одноместными предикаторными, а отношения многоместными.

4) Предикаторные символы синтаксически используют для образования формул, а семантически они обозначают предикаты ( например, xy, x Y)

Примеры:

1. Космонавт Гагарин – первопроходец космического пространства. По ЯПЛ- это субъектно-предикатное простое высказывание имеет вид P(f(a)), где P-означает логическое сказуемое,первопроходец космического пространства, f(a)- космонавт Гагарин ( т.е. а- Гагарин, f- космонавт).
   
2. Микросхема, диод и транзистор- множество с агрегатной точки зрения. Это высказывание на ЯЛП имеет вид P(a,b, c), где P- множество с агрегатной точки зрения, a,b,c- элементы множества- соответственно микросхема, диод, транзистор.
   

б) Логические операторы ( константы).

Логическими операторами в ЯЛП являются логические связи { , , ,  и кванторы , .

Пояснения:

1. Кванторам в естественном языке соответствуют кванторы слова типа « для всех» и «существует».
   
2. Иногда в ЯЛВ используют так называемый математический базис операторов, например , , , , , , , , , , , .
   
3. Связки и кванторы имеют следующий приоритет: , , , , , .
   

в) Вспомогательные символы

Вспомогательными ( разделительными) символами являются левая и правая круглые скобки, т.е. Р₃= , .


III. Языковые выражения , F.

В ЯЛП имеются два типа правильно построенных выражений из символов A_n- термы  и формулы F.

а) Термы .

Термы  являются символической записью предметов естественного языка.

Формально терм можно определить по инструкции:

• произвольная предметная константа является термом;
  
• произвольная предметная переменная является термом;
  
• если Ф – n-местная предметно-функциональная константа, а t₁…t_n- термы, то выражение Ф(t₁…t_n)- является термом;
  
• других термов нет, т.е. ничто не является термом ЯЛП;
  

Замечание:

1. предметные константы и предметные переменные называют простыми термами, а Ф(t₁…t_n)- сложными термами.
   
2. Символы, использованные в определении терма t_i , Ф – есть метасимволы ( это не символы объектного языка.
   
3. Терм называют замкнутым, если он не содержит предметных переменных.
   

Пример:

1) Записать на ЯЛП следующие выражения : 3, 5, 7+2.

Решение:

Пусть a, b, c, d – индивидные константы, соответствующие объектам 3, 5, 7, 2.

В этом случае a – простой терм, а f(b) и g(c, d)- сложные замкнутые термы, где f¹ – одноместная предметно-функциональная константа, соответствующая функтору  , а g²- двуместная предметно-функциональная константа, соответствующая функтору t.

2) С учетом обозначений объектов в примере 1 выражениям , ((7+3)), (7+7)+(2+2), 7+7+2+2 в ЯЛП соответствуют свободно замкнутые термы g²(f¹(а), х), f¹(g²(c, d)), g²(g²(c, c), g²(d, d)), g²(g²(g²(c, c), d),d)

3) Естественно-языковые выражения « Столица России», «Расстояние от Москвы до Тулы», «расстояние от столицы России до Тулы» в ЯЛП соответствуют замкнутые термы: f¹(а), g²(b,c), g²(f(а), c), где a,b,c- соответственно, Россия, Москва, Тула, f¹ «столица», g² «расстояние от… до…».


Предостережение

Символическая запись h²(g²(х, а)) не является термом, так как в скобках после двухместного предметно-функциональной константы h² стоит только один терм g²(х, а), а не два, как этого требует определение образования сложных термов. Не является термом и выражение Р¹(g²(х, а)), так как Р¹- предикаторная константа, а не функциональная.


б) Формулы F_n

Формулы ЯПЛ F_n являются символической записью логических форм высказываний и предикатов.

Индуктивное определение F_n:

1. Выражение Пⁿ (t₁…t_n) является формулой, если Пⁿ- n-местная предикаторная константа, а t₁…t_n- термы;
   
2. Если А- формулам, то  А- формула;
   
3. Если А и В – формулы, то (АВ), (АВ) и (АВ)- формулы;
   
4. Если А_(х)- формула, а х-свободная переменная, то х А(х) и  х А(х)- формулы;
   
5. Ничто иное не является формулой ЯЛП;
   

Пояснения:

1) В приведенном определении П, А, В являются символами метаязыка, значениями которых являются соответственно предикаторные буквы и формулы объектного ЯЛП.

2) Формула Пⁿ (t₁…t_n) называется элементарной (атомарной), а формулы пунктов 2, 3, 4 приведенного индуктивного определения принято называть сложными (молекулярными). Говорят, что сложная формула состоит из подформул (в пункте 3 это А и В, в 2 и 4 –А).

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