авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

«ОРЕНБУРГСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

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

В.А. СТЕНЮШКИНА

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

И ТЕОРИЯ АЛГОРИТМОВ

Рекомендовано Ученым советом Государственного образовательного учрежде-

ния высшего профессионального образования «Оренбургский государственный университет»в качестве учебного пособия для студентов экономических и есте ственнонаучных специальностей Оренбург 2004 ББК 22.12я7 С 79 УДК [510.5+510.6](075.8) Рецензент кандидат технических наук, доцент Ю.Н.Пивоваров Стенюшкина В.А.

C 79 Математическая логика и теория алгоритмов: Учебное пособие. Оренбург: ГОУ ОГУ, 2004. – 106 с.

ISBN Пособие предназначено студентам экономических и естественнонауч ных специальностей для выработки конструктивных знаний в области фо рмальной логики и алгоритмизации ББК 22.12я ISBN © Стенюшкина В.А., © ГОУ ОГУ, ЧАСТЬ 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА Введение Математическая логика – естественнонаучная дисциплина, изучающая математические доказательства и вопросы оснований математики.

Логика как искусство рассуждений зародилась в глубокой древности.

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

А – общеутвердительное суждение «Всякое S суть Р»;

Е – общеотрицательное суждение «Никакое S не суть Р»;

I – частноутвердительное суждение «Некоторые S суть Р»;

О – частноотрицательное суждение «Некоторые S не суть Р».

Пример «первой фигуры» силлогизма: «Все люди смертны. Кай – чело век. Следовательно, Кай смертен.»

Первый этап развития формальной логики – традиционная логика – дли лся два тысячелетия. Второй этап – современная логика - длится поныне. Дру гие имена этого этапа – символическая логика или математическая логика. Ос новы современной формальной логики заложили (середина XIX – начало XXв.в.) Дж. Буль, О. Морган, Г. Фреге, Дж. Пеано.

Традиционная логика опиралась на естественный язык, который из-за многозначности и аморфности требований к построению выражений и прида ния им смысла приводит к парадоксам. В средние века был распространен па радокс: “Сказанное Платоном – ложно, - говорит Сократ. – Сказанное Сократом – истинно, - говорит Платон”. Современная логика использует формальные те ории (ФТ), или исчисления.

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

Исчисление называется разрешимым, если существует алгоритм, позволяющий для любого высказывания определить, выводимо оно в этом исчислении или нет. Формальные теории являются развитием аксиоматического метода, приоб ретшего известность благодаря «Началам» Евклида (около 330 – 320 гг. до н.

э.). Предпринятое во второй половине XIX в. исследование аксиом евклидовой геометрии (ЕГ) показало, что система аксиом, данная в «началах» не полна. В 1899 г. Дж. Гильберт предложил первую достаточно строгую аксиоматику ЕГ.

К 1922 г. у Гильберта сложился план обоснования всей математики путем ее полной формализации и последующим «метаматематическим» доказательством непротиворечивости формализованной математики. А в 1931 году К. Геделем была доказана теорема о неполноте арифметики, из которой следовало, что для достаточно богатых по содержанию математических теорий не существует аде кватных формализаций. Тем не менее, вся дальнейшая работа над логическими основаниями математики в большой мере идет по путям, намеченным Гильбер том. Дело в том, что на практике формальные теории, описывающие содержа тельные объекты, задаются с помощью собственных аксиом, которые наряду с собственно предикатами и функторами содержат предикаты и функторы, свой ства которых аксиомами не описываются, а считаются известными в данной теории.

Язык, который мы изучаем (в данном случае язык ФТ), называется язы ком–объектом, а язык, на котором мы формулируем и доказываем различные результаты об этом языке – объекте, называется метаязыком. (Этот метаязык сам мог бы быть формализован и стать предметом исследования, которое, в свою очередь, проводилось бы на некотором метаязыке, и т. д.). Различию меж ду «выводом в языке–объекте» и «доказательством в метаязыке» соответствует различие между теоремой языка – объекта и метатеоремой языка. Слово «мета математика» употребляется, в частности, как название исследований логичес ких и математических языков–объектов.

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

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

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

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

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

Пример – Высказывание «Вода – продукт горения водорода» естествен но считать истинным, а высказывание «Все числа вида 2n+1 – простые» - лож ным.

В логике высказываний каждое высказывание отождествляется с его ис тинностным значением: «истина» (1) или «ложь» (0). Само установление ис тинностного значения отдельно взятого высказывания в логике высказываний не производится.

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

Рассмотрим наиболее распространенные логические операции /1/.

Отрицание – одноместная логическая операция («не») – по высказы ванию А определяет высказывание A («не А» или «неверно, что А»), которое считается истинным тогда и только тогда, когда А – ложно.

Пример – А:=«Число 10 делится на 5», А:=«Неверно, что число 10 дели тся на 5».

Отрицание обозначается также символом « ¬ » или надчёркиванием.

Конъюнкция – двухместная логическая операция («и») – по высказы ваниям А, В определяет высказывание А В («А и В»), которое считается ис тинным тогда и только тогда, когда оба высказывания А, В истинны.

Дизъюнкция – двухместная логическая операция («или») – по выска зываниям A, B определяет высказывание AВ («A или B»), которое считается истинным тогда и только тогда, когда хотя бы одно из высказываний A, B – ис тинно.

Пример – A:= «Дождь кончился», B:= «Птицы запели», A B:= «Дождь кончился, или птицы запели».

Импликация – двухместная логическая операция («если…, то…») – по высказываниям А, В определяет высказывание АВ («если А, то В»), кото рое считается ложным тогда и только тогда, когда А - истинно, В – ложно.

Пример – Пусть А:= «2*2=5» - ложно, В:= «Рим столица Италии» - ис тинно. Тогда A:=”Если 22=5, то Рим – столица Италии” – истинно.

В импликации АВ высказывание А называется посылкой, высказыва ние В – заключением. Из определения импликации следует, что в случае ис тинности обоих высказываний А, АВ высказывание В – истинно. Это соот ветствует основному из применяемых в математике правил вывода - Modus Po nens (Правило отделения).

Эквиваленция – двухместная логическая операция («если и только если…, то…») определяет высказывание А В («если и только если А, то В»), которое считается истинным тогда и только тогда, когда А, В имеют одинако вые истинностные значения (оба истинны или оба ложны).

Пример – «Квадратная матрица имеет обратную (А) если и только если определитель матрицы отличен от нуля (В)». Это высказывание истинно, если считать, что А, В истинны.

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

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

1.2 Булевы функции. Истинностные таблицы Булева функция – n-местная функция из {0,1}n в {0,1}. Каждой n местной логической операции взаимно однозначно соответствует n-местная булева функция y=f(x1,…,xn), x1,…,xn, y{0,1}, где двоичные переменные x1,…,xn, y соответствуют высказываниям (операндам и результанту) и называю тся пропозициональными переменными. Другие названия булевых функций:

логические функции, функции истинности.

Булеву функцию n переменных можно задать, таблицей истинности (таблица 1.1):

Таблица 1. x1 … xn f (x1,…,xn) 0 … 0 f (0,…,0) 0 … 1 f (0,…,1) … … … … 1 … 1 f (1,…,1) Каждый набор значений аргументов называется интерпретацией булевой функции, а ее соответствующее значение – истинностным значением.

Если число переменных n, то число различных наборов значений аргу ментов равно 2n, а число различных булевых функций – 2 n Булевы функции одной переменной: yi=fi(x), i=0..3 (таблица 1.2).

Булевы функции двух переменных: yi=fi(x1,x2), i=0..15. Приведём табли цы некоторых двухместных булевых функций (таблица 1.3).

Таблица 1. x1 y0=0 y1=x y3= y2= x 0 0 0 1 1 0 1 0 Таблица 1. x1 0 0 1 1 Название фу 1 нкции x2 0 1 y0=0 0 0 0 0 Константа Конъюнкция y1=x1 x2 0 0 0 y6=x1+x2 Сложение по 0 1 1 модулю Дизъюнкция y7=x1x2 0 1 1 y8=x1x2 Стрелка Пир 1 0 0 са y9=x1x2 Эквиваленция 1 0 0 y13=x1x2 Импликация 1 1 0 y14=x1/x2 Штрих Шеф 1 1 1 фера y15=1 1 1 1 1 Константа При построении таблиц истинности более сложных высказываний нуж но последовательно использовать таблицы истинности логических операций.

Пример – Составить таблицу истинности для высказывания А В Решение даётся таблицей 1.4.

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

Нормальная форма 2.1 Конъюнктивная нормальная форма. Дизъюнктивная нормальная форма x, = 1, Пусть x – двоичная переменная. Введем обозначение x = x, = 0.

Тогда функции и x1... x n, x1... x n, где (1,…,n) – двоичный набор, а 1 n 1 n x1,…, xn – двоичные переменные (не обязательно различные) называются соот ветственно элементарной конъюнкцией, элементарной дизъюнкцией.

3)=(0,1,1). x1 1 x 2 2 x 3 3 x1 x 2 x 3 Пример–Пусть (1, 2, Тогда элементарная конъюнкция.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Пример - ( x1 x2 ) ( x1 x2 ) - дизъюнктивная нормальная форма.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

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

x y = x y, x y = ( x y ) ( x y ) = ( x y ) ( x y );

затем продвинуть знак отрицания к переменным с учетом равенств x y = x y, x y = x y;

устранить двойное отрицание, x = x. так как, Затем, используя одно из равенств: x(yz)=(xy)(xz), x(yz)=(xy)(xz) непо средственно получить дизъюнктивную или конъюнктивную нормальную фо рму.

Пример – Дана булева функция: ( x1 x 2 ) x3.

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

( x1 x 2 ) x 3 = (( x 1 x 2 ) x 3 ) (( x 1 x 2 ) x 3 ) = (( x1 x 2 ) x 3 ) (( x 1 x 2 ) x 3 ) = ( x 2 x 3 ) (( x 1 x 2 ) x 3 ) = ( x1 x 3 ) ( x 2 x 3 ) ( x 1 x 2 x 3 ).

Получена конъюнктивная нормальная форма.

2.2 Совершенная нормальная форма. Теорема существования и единственности Совершенной дизъюнктивной нормальной формой по переменным x1,…, xn называется дизъюнктивная нормальная форма, у которой все элементарные конъюнкции содержат каждую переменную ровно по одному разу (в прямом или инверсном виде), и все конъюнкции различны.

Совершенной конъюнктивной нормальной формой по переменным x1,…, xn называется конъюнктивная нормальная форма, у которой все элемента рные дизъюнкции содержат каждую переменную ровно по одному разу (в пря мом или инверсном виде), и все дизъюнкции различны.

Пример - (x1 x2 ) ( x1 x2 ) - совершенная конъюнктивная нормальная форма по x 1, x2.

Теорема (существования и единственности) Для любой n-местной буле вой функции f(x1,…, xn) 0 существует единственная совершенная дизъюнк тивная нормальная форма, реализующая эту функцию, и существует единст венная совершенная конъюнктивная нормальная форма, реализующая эту фун кцию.

Доказательство Проверим выполнение следующего тождества по двоич ным переменным x1,…, xn:

1 n f ( x x,..., x n ) (,..., ) f ( 1,..., n ) x1... x n, (2.1) 1 n где правая часть есть дизъюнкция (по всем двоичным наборам (1,…, n)) функций F ( 1,..., n ) = f ( 1,..., n ) x1 1... xn n.

Пусть (x1,…, xn)=(1,…, n) 0,1n. Слева имеем f (1,…, n). Заме 1... n = тим, что для правой части будет выполняться равенство 1 n тогда и только тогда, когда (1,…,n)=(1,…, n). Это означает, что дизъ юнктивные члены правой части, для которых (1,…,n)(1,…, n), можно опус тить. Правая часть становится равной f(1,…, n) 1=f(1,…, n). Итак, слева и справа в (2.1) имеем f(1,…, n). Если f(x1,…, xn) 0, то формула (2.1) эквивале нтна формуле 1 n f ( x1,..., x n ) (,..., ( x1... x n ). (2.2) n ) f ( 1,..., n ) = Выражение справа есть совершенная дизъюнктивная нормальная форма.

Существование совершенной дизъюнктивной нормальной формы доказано.

Единственность доказывается от противного.

Для булевой функции f(x1,…,xn) по тождеству (1) имеем:

f(x 1,…,x n) = ( 1,…, n ) (f( 1,…, n) (x 1 1,…,x n n) (2.3) Взяв отрицание от обеих частей (2.3) и проведя тождественные преобра зования, получим:

f(x1,…xn)= (1,…,n) (f(1,…,n) x11…xnn) (2.4) Если f(x1,…, xn) 1, то справедливо тождество:

n f ( x1,..., x n ) ( ( x1 1... x n ) (2.5) 1,..., n ) f(д1,...,дn ) = Выражение в правой части (2.5) является совершенной конъюнктивной нормальной формой. Существование совершенной конъюнктивной нормальной формы доказано. Единственность также имеет место. Теорема дает способы по строения совершенной нормальной формы.

Пример –Пусть булева функция y=f(x1,x2,x3) задана таблицей 1.5.

Таблица 1. x1 0000 x2 0011 x3 0101 Y 0110 Тогда СДНФ и СКНФ – имеют соответственно вид:

( x1 x2 x3 ) ( x1 x 2 x 3 ) ( x1 x2 x 3 ) ( x1 x 2 x3 );

( x 1 x 2 x 3 ) ( x 1 x 2 x 3 ) ( x1 x 2 x 3 ) ( x1 x 2 x 3 ).

Следствие Любая булева функция выразима через функции:,,.

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

Примеры полных систем в множестве булевых функций:

1),, ;

2), ;

3), ;

4);

5).

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

x1 x2 = x1 x2 = x1 x2, которые можно принять за определение этих x1 / x2 = x1 x2 = x1 x2, функций.

2.3 Применение алгебры высказываний к описанию релейно контактных схем (РКС) Под релейно-контактными схемами понимают схематическое изображе ние какого-либо устройства, состоящего из соединенных между собой двухпо зиционных переключателей. Двухпозиционные переключатели могут нахо диться в двух состояниях: в замкнутом (ток проходит) и в разомкнутом (ток не проходит). Такие схемы можно описать в терминах алгебры высказываний. Ка ждому переключателю ставиться в соответствие высказывание, истинное при замкнутом переключателе и ложное – при разомкнутом. При этом удобно пере ключатели обозначать теми же буквами, что и высказывания. Если два пере ключателя работают так, что один из них замкнут, когда другой разомкнут, и наоборот, то они обозначаются соответственно А и.

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

Пример – Упростить схему (рисунок 2.1).

А А А А1 А2 А А1 А2 А Рисунок 2. Решение Составляем по схеме высказывание и упрощаем его:

(( А1 А3 ) А2 ) ( А1 А2 А2 ) ( А1 А2 А3 ) = ( А1 А2 ) ( А3 А2 ) ( А1 А1 ) ( А2 А3 ) = ( А1 А2 ) А3 ( А2 А2 ) = ( А1 А2 ) А Упрощенная схема (рисунок 2.2) имеет три переключателя вместо девя ти в исходной.

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

3.1 Предикаты. Функторы N-местным предикатом на множестве M называется n-местная функция Р(x1,…, xn), аргументы которой принимают значение из множества M, а сама функция принимает значения из множества {0(«ложь»), 1(«истина»)}. При n= предикаты называются унарными, n=2 – бинарными, n=3 - тернарными и т.д.

Нульместный предикат рассматривается как высказывание. Предикат задает отношение нам.

Примеры 1 M={1,2,3,…} – множество натуральных чисел;

а) Р(x):= «x делится на 2». Р(2)= «истина», Р(3)= «ложь»;

б) Р(x1, x2): «x1 x2». Р(1,2)= «ложь», Р(3,2)= «истина».

2 M=R=(-,+) – множество действительных чисел :

Р(x1, x2, x3)= «истина», x1+x2+x3=1, «ложь», в противном случае;

Р(1,0,0)=«истина»,Р(0,0,0)=«ложь» и т.д.

Предикат Р(x1,…, xn), определенный на M, называется тождественно ис тинным на M, если определяющая его функция Р(x1,…, xn)1;

тождественно ложным, если Р(x1,…, xn)0, выполнимым, если Р(x1,…, xn) 0.

Пример – Предикат Р(x):= «|х|0», определенный на R, тождественно ис тинен на R.

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

Определенные элементы a1, a2,… из M называются предметными посто янными, а неопределенные элементы x1,…, xn из M – предметными переменны ми. При замещении предметной переменной хк, к1..n, предметной постоянной аM n-местный предикат Р(x1,…, xn) превращается в (n-1) местный предикат Р(х1,…,хк-1,a,хк+1,…,хn) и от хк уже не зависит. Если заместить все переменные постоянными, то получится высказывание, или нульместный предикат.

Пример - Р(x1, x2, x3):= «x1+x2=x3» - трехместный предикат;

Р(x1, x2, 5):= «x1+x2=5» - двухместный предикат;

Р(2,3,5):= «2+3=5» - высказывание.

N-местным функтором на множестве M называется n-местная функция f(x1,…, xu), принимающая, как и аргументы, значения из множества M (то есть n-местный функтор задает n-местную операцию на M).

3.2 Операции над предикатами. Кванторы Пусть Р(х), Q(x), хМ, для которых предикат Р(х) ложен.

Отрицанием предиката Р(х) на множестве M называется предикат Р(х) на том же множестве, истинный для тех и только тех значений хМ, для кото рых предикат Р(х) ложен.

Конъюнкцией предикатов Р(х), Q(x) на множестве M называется преди кат Р(х)Q(x) на том же множестве, истинный для тех и только тех значений хМ, для которых оба предиката Р(х), Q(x) истинны.

Дизъюнкцией предикатов Р(х), Q(x) на множестве M называется преди кат Р(х)Q(x) на том же множестве, истинный для тех и только тех значений хМ, для которых истинен хотя бы один из предикатов Р(х), Q(x).

Подобным образом вводятся предикаты Р(х) Q(x), Р(х)Q(x).

Пример – Даны предикаты: Р(х):= «х5», Q(x):= «х2», х{1,2,3,4,5} =М. Тогда Р(х):= «х5», Р(х)Q(x):=«2х5»;

Р(1)Q(1)=0, Р(2)Q(2)=1.

Над многоместными предикатами операции определяются аналогичным образом. Так, отрицанием n-местного предиката на некотором множестве М называется n-местный предикат Р(x1,…, xn) на том же множестве М, истинный для тех и только тех наборов значений аргументов, для которых предикат Р(x1,…, xn) ложен.

Для предикатов вводится также специфические логические операции, или кванторы, - («каждый» или «для всех») – квантор общности и («сущес твует» или «для некоторых») – квантор единичности.

Пусть Р(х), хМ – одноместный предикат. Тогда запись х Р(х) («для любого х Р(х)») означает высказывание, истинное, если Р(х) – тождественно истинен на М, и ложное, если Р(х) не является тождественно истинным на М;

запись х Р(х) («существует х такой, что Р(х)») означает высказывание, истин ное, если Р(х) выполним на М, и ложное, если Р(х) невыполним на М.

Пример – Если Р(х):= «х2=1», хМ=(-,+), то х Р(х)=0, х Р(х)=1.

хР( х) = х Р( х), хР( х) = х Р( х).

Специфические равносильности:

Дадим определение квантификации для многоместных предикатов.

Пусть Р(х, х1,…,хn) – (n+1) – местный предикат, определенный на мно жестве M (n0). Тогда запись х Р(х, х1,…,хn) означает n – местный предикат на М, зависящий от х1,…,хn (и не зависящий от х) и принимающий значение «истина» для тех и только тех значений а1,…,аnМ переменных х1,…,хn, для которых одноместный предикат Р(х, а1,…,аn) является тождественно истинным на М;

запись х Р(х, х1,…,хn) означает n-местный предикат на М, зависящий от х1,…,хn (и независящий от х) и принимающий значение «истина» для тех и то лько тех значений а1,…,аnМ переменных х1,…,хn, для которых одноместный предикат Р(х, а1,…,аn) является выполнимым на М. Предикат Р в записях х Р х Р называется областью действия квантора.

Пример – Пусть Р(х,у):= «ху», х, уR – двухместный предикат на мно жестве действительных чисел. Тогда предикаты х (xy), у (xy), х (xy), у (xy) - одноместные предикаты (первые два – тождественно ложные, вто рые два – тождественно истинные), а предикаты х у (xy), у х (xy), xy(хy), y(xy) нульместные (ложные). Ещё можно составить че тыре нульместных предиката (они окажутся истинными).

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

Примеры 1 Пусть предикат Р(х) задан таблицей на множестве М={1, 2}:Р(1)=1, Р(2)=0. Тогда высказывание хР(х) имеет значение «истина».

2 Определить истинностные значения высказывания х(Р(х) Q(f(х), а) если х{1,2}=М, а=1, а предикаты и функтор заданы таблицами 2.1 и 2.2.

Таблица 2.1 Таблица 2. 1 2 1 1 2 x x f 2 1 у 1 2 1 (х) Р 0 1 Q 1 1 0 (х) Решение В результате подстановки значения константы получаем выс казывание х(Р(х) Q(f (х), 1). Строим вспомогательную таблицу 2.3.

Таблица 2. х 1 Q(f(х),1) 0 1 Р(х)Q(f(х),1) По последней строке заключаем, что исходное высказывание имеет зна чение 1 в заданных условиях.

3.3 Термы. Атомы Константы, переменные или функторы называются термами. Предикат, аргументами которого являются термы, называется также атомом.

3.4 Свободные и связанные вхождения переменных Вхождения переменных в атом называются свободными. Свободные вхождения переменных в предикаты Р и Q остаются свободными в предикатах Р, РQ. Вхождение переменой в предикат хР и хР называются связанными.

Если вхождения переменных (отличных от х) были свободными в пре дикате Р, то они остаются свободными и в предикатах хР и хР. Одна и также переменная может иметь в одном и том же предикате как свободные, так и свя занные вхождения. Вхождение х в цепочку х, х, считается связанным.

1 В предикате х(Р(х,у)уQ(у)R(х) первое и второе вхождения пере менной х связаны, третье - свободно, переменная у связана.

2 Дан предикат х(Р(х,у,z)уQ(х,у)Q(х,у) S. Здесь Р(х,у,z) - трехмес тный, Q(х,у) - двухместный, S - нульместный предикаты. Требуется определить истинностное значение данного предиката при условиях: М={a, b};

S = 0;

сво бодные вхождения переменных заменяются значениями -х=b, у=а, z=a;

преди каты Р, Q заданы таблицей 2.4.

Таблица 2. х a a a a b b b b у a a b b a a b b z a b a b a b a b Р 0 1 1 0 0 1 0 Q 0 0 0 0 0 0 1 Решение Подставляя значение свободных предметных переменных и значение предиката S, получим высказывание х(Р(х,а,а) уQ(х,у)Q(b,а) 1, которое в силу Q(b, а)=0 заменяется на высказывание х(Р(х,а,ау Q(х,у).

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

Таблица 2. уQ(х, х P(х,а,а) у) а 0 b 0 4 Формальные теории 4.1 Определение формальной теории Формальная теория (ФТ) - это четверка Т = (S, F, А, R) /2/, где S - алфавит - множество символов;

F - множество формул - множество правильно построенных цепочек символов из S;

А - множество аксиом подмножество множества F;

R - множество правил вывода - множество отношений на множестве F.

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

если бесконечно, то задается схемами и правилами их конкретизации. Множество R обычно конечно;

будет предполагаться, что F n+1 (при некотором n), где Fn+1 - (n+1)-ая декартова степень множества F.

4.2 Выводимость. Разрешимость Пусть F1,..., Fn, G- формула формальной теории Т, то есть F1,..., Fn,GF и пусть имеется правило R такое, что (F1, …, Fn, G). Тогда формула G называется непосредственно выводимой из формул F1,..., Fn по правилу.

F,..., Fn, при этом формулы F1,...., Fn называются посылками, Запись: G а формула G - заключением.

Формула G называется выводимой из формул F1,..., Fn, в формальной те ории Т, если существует последовательность формул Е1,...., Ek такая, что Еk= G, а любая из Еi, i = 1...(k - 1), есть либо аксиома, либо одна из исходных фор мул F1,...,Fn, либо непосредственно выводима из подмножества ранее получен ных формул Ej1,…, Ej1, j1,...,jl i. Последовательность Е1,...., Еk называется при этом выводом формулы G из формул F1,..., Fn в теории Т.

Запись: F1,...,Fn |…G;

формулы F1,..., Fn, называются гипотезами, фор мула G - тезисом. Знак теории Т можно опускать.

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

Запись: | G (множество гипотез пусто).

При добавлении гипотез выводимость сохраняется, то есть если Г («га мма») и («дельта») - множества формул, причем Г| TG, то есть Г, | T G.

Примечание - По отношению к теоремам формальной теории теоремы о формальной теории называются метатеоремами.

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

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

4.3 Интерпретация формальных теорий Интерпретацией I формальной теории Т в область интерпретации на зывается отображение всех множеств и отношений на них формальной теории Т в множество объектов и связей между ними области.

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

Интерпретация I называется моделью формальной теории Т, если все те оремы этой теории выполняются в интерпретации I (то есть для всех выводи мых из аксиом формул теории Т соответствующие высказывания в области истинны).

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

Формула формальной теории называется тождественно ложной, или противоречием, если она ложна в любой интерпретации.

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

4.4 Непротиворечивость. Полнота. Независимость Формальная теория называется непротиворечивой, если в ней не являю тся одновременно выводимыми формула F и F.

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

Система аксиом непротиворечивой теории Г называется независимой, ес ли никакая из аксиом не выводима из остальных по правилам вывода теории Т.

5 Исчисление высказываний Задача исчисления высказываний (ИВ) - описание всех тождественно истинных формул.

5.1 Определение ИВ Классическое ИВ - это формальная теория L, в которой:

- алфавит есть множество символов:

1) а, b,..., а1, b1,...- (пропозициональные) переменные;

2), - связки;

3) (, ) - служебные символы;

- множество формул есть множество цепочек символов, задаваемых син таксическими правилами:

1) переменные есть (пропозициональные) формулы;

2) если А,В - формулы, то ( А), (А В) - формулы;

- множество аксиом задается схемами (один из вариантов):

А1: = (А (В А);

А2: = ((А (В С )) ((А В) (АС)):

А3: = (( В А) ((В А В));

A, A B -множество правил задается схемой: MP (Modus Ponens), B где А, В, … - любые формулы. Для получения конкретных правил и ак сиом используются подстановки формул вместо метасимволов А, В,.... Знак подстановки: «/».

В дальнейшем используются синтаксические сокращения:

АВ: = (А В);

А,, В:= А В.

5.2 Выводимость. Производные правила вывода Выводимость формул в L, как в ФT, доказывается путем построения со ответствующего вывода. Формулы вывода будем записывать в столбец, а спра ва - указывать основание для включения этих формул в вывод. В качестве при мера рассмотрим вывод из аксиом.

Теорема 5.1 |LА А.

Доказательствo 1) (А ((А А) А));

А1: {А А/В};

2) ((А ((А А) А)) ((А (АА))(AA));

А2: {А АВ, А/С};

3) ((А (А А )) (А А));

МР: 1,2;

4) А (А А);

А1: {A /В};

5) А А;

МР: 4, Всякую доказанную выводимость можно использовать как новое, произ водное правило вывода.

Теорема 5.2 A|LB А.

Доказательство:

1) А;

гипотеза;

2) А (В В);

A1;

3) В А;

МР: 1,2.

A Доказана выводимость I mp правило введения импликации.

BA 5.3 Теорема дедукции Теорема Если Г, А |L...В1, то Г |L... А В и обратно. Здесь Г - некото рое множество формул.

Доказательство прямой теоремы. Пусть Е1..., Еn – вывод - В из Г, А. При этом Еn =В. Применяя метод математической индукции по i (1 i n), то есть покажем, что Г|L АЕi;

тогда при i =n прямая теорема будет доказана. Итак, пусть i = 1 (база индукции).

Рассмотрим вывод:

1) Е1;

аксиома или посылка:

2) Е1 (А Е1);

А1:{А/В, Е1 /А};

3) А Е1;

МР: 1,2.

То есть Г|LА Е Далее по методу предположим, что Г|LА Еi для всех i k и рассмот рим Ek.. Здесь возможны случаи: либо Ek аксиома или посылка, тогда доказа тельство повторяет предыдущее, либо Еk получена по правилу МР из Ei, Ej;

причем i, j k, и Ej: = Еi Еk. В последнем случае, так как i, j k, то для Ei, Ej имеются выводы Г|LА Еi и Г|LА (Еi Еk ). Объединим эти выводы в один и достроим его до требуемого вывода:

1) A Ei;

2) A (Ei Ek);

3) (A (Ei Ek)) ((A Ei) (A Ek));

A2: {Ej./В, Ek /Сj};

4) (А Еi) (А Аk);

МР: 2 3;

5) A Ek МР: 1 4.

Итак, для Ek вывод построен. Тогда по методу математической индукции заключаем, что для любого n имеет место выводимость Г|LА Еn. Поскольку Еn:=В, то Г|LАB. Прямая теорема доказана.

Доказательство обратной теоремы. Пусть имеем вывод Г|LА B, сос тоящий из формул. Достроим его:

1) А В;

2) А;

гипотеза;

3) В;

МР: 2, 3.

Таким образом, имеет место выводимость Г|LАB. Обратная теорема доказана. Теорема доказана.

Cледствие Если А|LВ, то |L A В и обратно. Доказательство Г: =.

5.4 Применение ТД Теорема 5.3 Имеет место выводимость: А В, В С|LА С.

Доказательство Сначала докажем выводимость А В, В С|L С:

1) А В;

гипотеза;

2) В С;

гипотеза;

3) А;

гипотеза;

4) В;

МР: 3,1;

5) С;

МР: 4,2.

Вывод для С построен. Теперь по теореме дедукции заключаем, что А В, В С|LА С. Теорема доказана. Эта теорема дает производное правило A B, B C Tr, называемое правилом транзитивности:

AC Теорема 5.4 Имеет место выводимость: А (В С), В |L А С.

Доказательство Сначала доказываем выводимость А(ВС), В,А|LС:

1) A (В С);

гипотеза;

2) А;

гипотеза;

3) В С;

МР: 2,1;

4) В;

гипотеза;

5) С;

МР: 4,3.

Вывод для С построен. Теперь по теореме дедукции заключаем, что имеет место выводимость А (В С), В|L А С. Теорема доказана. Теорема A ( B C ), B дает производное правило Sec правило сечения.

AC 6 Интерпретация исчисления высказываний 6.1 Интерпретация исчисления высказываний в алгебру высказываний Интерпретация ИВ в алгебру высказываний задается приписыванием в качестве значений:

-каждой пропозициональной переменной конкретного высказывания (с его истинным значением);

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

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

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

ложное - в противном случае.

6.2 Равносильные формулы Две формулы ИВ называются равносильными, если они имеют одинако вые истинностные значения во всех интерпретациях.

Запись: А=В («А равносильно В»).

Имеют место следующие равносильности:

1 Коммутативность конъюнкции, дизъюнкции:

А В = В А, А В= В А.

2 Ассоциативность конъюнкции, дизъюнкции:

А (В С)= (А B) C, А (В С) = (А В) С.

3 Дистрибутивность конъюнкции относительно дизъюнкции, дизъюнк ции относительно конъюнкции:

А(ВС) = (АВ)(АC)=(A(ВС)=(АD)(АС).

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

A B = A B, A B= A B, 5 Закон двойного отрицания.

A = A.

6 Закон исключенного третьего, закон противоречия:

А A =1, А A =0.

7 Закон идемпотентности:

А А = А, А А = А.

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

А (А В) = А, А (А В)=А.

9 Элиминация импликации и эквивалентности:

A B = A B, A B = (A B) (B A) = (A B) (A B) 10 Законы констант:

А 1 =А, А 1= 1, 1 = 0, А 0 = 0, A 1 = A, 0 = 1.

Все равносильности можно проверить таблично. Заметим, что свойство 2 позволяет бесcкобочные записи А1 … An или А1... Аn.

Пример - В соответствии с определением основных логических опера ций ( и соответствующих им БФ) составим таблицу 6.1.Сравнивая столбцы для A B и A B, заключаем, что A B = A B, то есть выполнен один из зако нов де Моргана.

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

Таблица 6. А В А A A B A В 0 0 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 7 Классификация формул логики высказываний 7.1 Типы формул Формула в ЛВ называется тождественно-истинной, или тавтологией, ес ли она истинна в любой интерпретации Формула ЛВ называется тождественно-ложной, или противоречием, ес ли она ложна в любой интерпретации.

Очевидно, формула тождественно истинна тогда и только тогда, когда А тождественно ложна.

Формула ЛВ называется выполнимой если она истинна хотя бы в одной интерпретации.

Пример – Формула Р P выполнима, так как, например 0 1 = 1.

Основные примеры тавтологий:

Р Р (закон тождества);

P P (закон исключенного третьего);

P P (закон противоречия);

P P (закон двойного отрицания);

P (Q Р) (истина из чего угодно);

P (P Q) (из лжи что угодно);

(Р Q) Р Q (Modus Ponens);

(Р Q) Q P (Modus Tollens);

(Р Q) (Q R) (Р R) (закон силлогизма);

(Р Q) (Q P ) (закон контрапозиции).

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

Пример - Составить таблицу истинности для следующего высказывания:

(P Q) (Q P). Решение даётся таблицей 7.1.

7.2 Логическое следствие. Логическая эквивалентность Формула ЛВ называется логическим следствием формулы А, если В ис тинна во всех интерпретациях, в которых А истинна. Запись: А В («из А ло гически следует В»).

Пример - Имеет место логическое следование Р (Q Р) (Таблица 7.1).

Доказательство. Если Р=1, то как известно, QР=1 при любом Q (01=1,11=1).Тогда имеем очевидное следование 1 1.

Теорема Для того, чтобы А В необходимо и достаточно, чтобы фор мула А В были тавтологией.

Доказательство Необходимость Пусть А В. Тогда по определению ло гического следствия, если А = 1, то В = 1, то есть невозможен набор (А, В) = (1, 0). Это означает по определению импликации, что А В - тавтология.

Таблица 7. Р Р ( P Q) (Q Q Q Q 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 1 Достаточность Пусть А В – тавтология. Это означает, что (А, В) (1, 0), то есть, если А = 1, то В = 1. Тогда по определению логического следствия А В. Теорема доказана.

Формула В называется логическим следствием формул А1, …Аn, если В является логическим следствием формулы А1 … Аn, то есть А1 … Аn В.

Запись: А1,..., Аn В.

Теорема Для того, чтобы А1 … Аn В, необходимо и достаточно, чтобы формула А1 … Аn В была противоречием.

7.3 Подстановка Если А - некоторая формула, в которую входит подформула В, то при меняется запись: А (...В...).

Если С - некоторая формула, которую подставляют формулу А вместо всех вхождений В, то применяется запись: А (...В...) {С//В}. В случае подстано вки необязательно всех вхождений символ «//» заменяется на «/».

Теорема 7.1 Если А (...х...) – тавтология и С - любая формула, то А (...х...) {С//х } – тавтология. Здесь В: =х).

Теорема 7.2 Если А (...В...) и С = В («равносильно»), то А (...В...) = А (...В...) {С/ В }.

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

Две формулы логики высказываний называются логически эквивалент ными, если каждая из них является логическим следствием другой. Запись: А В («А логически эквивалентно В»).

Теорема Для того, чтобы А В необходимо и достаточно, чтобы фор мула А В была тавтологией.

Доказательство. Если А = 1, то из А В следует, что В = 1. Если В = 1, то из В А следует, что А = 1 (по одной из двух предыдущих теорем). Это означает, что А = 1, тогда и только тогда, когда В = 1, то есть А = В во всех ин терпретациях, и по определению эквиваленции А В = 1 во всех интерпрета циях. Теорема доказана.

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

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

А1,…, Аm А В, (8.1) где А1, …, Аm – аксиомы, А В - теорема (не высказывание).

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

Для любой пары взаимно- обратных теорем может наблюдаться один из случаев:

а) обе теоремы верны;

б) прямая теорема верна, обратная неверна;

в) прямая неверна, обратная верна;

г) обе теоремы неверны.

Примеры 1 Пусть А:=«Число делится на 4»;

В:=«Число делится на 2». Тогда прямая теорема А В верна, обратная В А неверна.

2 Пусть А: = «Фигура есть квадрат», В: = «Фигура есть ромб». Тогда и прямая и обратная теоремы неверны.

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

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

Пример - Если А:=«Число делится на 3», В:=«Сумма цифр числа делится на 3», то А есть необходимое и достаточное условие для В.

Теоремы противоположная и обратная противоположной Теоремы вида А В и В А называются взаимно противоположными.

Пример - Если А В:=«Если функция дифференцируема (А), то она не прерывна (В)», то А В:=«Если функция не является дифференцируемой (А), то она не является непрерывной (В)». Как известно, в данном случае теорема АВ верна, теорема АВ неверна.

Закон контрапозиции Пусть А В – прямая теорема. Ей соответствуют теоремы: В А – обра тная теорема, А В – противоположная, B A обратная противоположной.

Теорема Если прямая теорема верна, то верна обратная противополож ной. Обратно, если теорема, обратная противоположной верна, то прямая верна.

Доказательство Известна тавтология (А В) (В А) – (закон контра позиции, - то есть (А В) ( B A ), и первая часть теоремы доказана.

Для B, A эта часть теоремы принимает вид B A (АВ) – тавтоло гия, и вторая часть, а вместе с ней теорема доказана.

Примечание - Теорема о теоремах называется метатеоремой по отноше нию к этим теоремам.

Методы математических доказательств Обратимся к схеме (8.1). Обычный способ доказательства теоремы А В состоит в том, что А принимают в качестве еще одного допущения, то есть приходят к схеме:

А1, …, Аn, А В (8.2) Основанием для такого перехода служат равносильности: А1 … Аn (А В)= A1 … An A B = А1 … Аn А В.

По способу проведения доказательства в математике делятся на два вида:

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

9 Свойства исчисления высказываний 9.1 Полнота Имеют место следующие метатеоремы.

Теорема 9.1 Всякая теорема исчисления высказываний есть тавтология.

Теорема 9.2 Всякая тавтология является теоремой исчисления высказыва ний.

Таким образом, теоремами теории L являются тождества - истинные фор мулы и только они. А это означает, что формальная теория L, то есть классиче ское исчисления высказываний, является полной.

9.2 Непротиворечивость Из теоремы 9.1 следует, что теория L непротиворечива. Действительно.

Любая теорема в L есть тавтология. Отрицание тавтологии не есть тавтология, то есть в L нет одновременной выводимости теоремы и ее отрицания, что соот ветствует определению непротиворечивости формальной теории.

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

9.4 Исследование системы аксиом ИВ. Независимость Подмножество множества всех аксиом данной ФТ называется незави симым, если ни одна из формул не может быть выведена с помощью правил вывода из аксиом, не входящих в.

Известно, что каждая из схем аксиом А1, А2, А3 независима. Эта система аксиом предложена П.С. Новиковым;

она весьма проста, но существует много других систем, работающих тоже хорошо.

Примеры 1 Гильберт, Аккерман, 1938:

- связки:, ;

- аксиомы: АА А;

А АВ;

АВ ВА, (В С) (АВ АС);

-правило: Modus Ponens.

2 Россер, 1953:

- связки:, ;

- аксиомы: А А А;

А А В А;

(А В) ( ( В С) (С А);

-правило: Modus Ponens.

3 Клини, 1952:

связки:,,, ;

- аксиомы:

А (В А) ;

А (ВС)) ((АВ) (А С);

А В А;

А В А;

А (В (АВ));

А (А В) ;

В (А В);

А С) ( (ВС) ( ( А В) С ));

(А В) ( ( А В) А ) ;

АА;

-правило: Modus Ponens.

10 Исчисление предикатов Задача исчисления предикатов (ИП) – описание всех тождественно- ис тинных предикатных формул.

10.1 Определение исчисления предикатов Классическое исчисление предикатов первого порядка- это формальная теория К, в которой:

-алфавит есть множество символов:

1)a,b, …, a1,b1, …, и x,y,…,x1,y1,… - (предметные) константы и предмет ные переменные соответственно;

2)n, Qn, …,1n, Q1n, … и fn, gn, …, f1n, g1n, …, n= 0, 1,2, …) – n – мест ные (предметные) предикатные переменные и (предметные) функциональные переменные соответственно;

3), - связки;

4), - кванторы;

5)(,),, - служебные символы;

-множество формул есть множество цепочек символов, задаваемых син таксическими правилами:

1)(предметные) константы и (предметные) переменные, как цепочки, суть термы;

2) если t1,…,tn – термы, fn- n –местная функциональная переменная, то це почка fn (t1,…,tn) – терм;

3)если t1,…,tn – термы, Pn – n – местная предикатная переменная, то цепо чка Pn(t1,…,tn) – атом;

4)атом есть формула;

5)если F, G - формула, x – ( предметная) переменная, то цепочки ( F), (x F), ( x F), (F G) – тоже формулы;

-множество аксиом ( один из вариантов) задается схемами:

1)схемы вида А1, А2, А3 исчисления высказываний (но с предикатными формулами);

2) P1: = x F(F( F( t);

P2: = F( t) x (x), где t-терм, свободный для переменной x в формуле F;

-множество правил вывода задается схемами:

F, F G 1) MP, G G F ( x) 2) R, G xF ( x) F ( x) G 3) R, xF ( x) G где формула F содержит свободные вхождения переменной x, а формула G их не содержит.

10.2 Вхождение переменных в формулы ИП Определение свободного и связанного вхождения переменных в формулы ИП аналогично (по синтаксису) определению для предикатов и рассмотрено в алгебре предикатов. То же относится и к понятию области действия кванторов.

Формула ИП, не содержащая свободных вхождений переменных, называ ется замкнутой.

Пусть F – формула, t – терм. Если никакое свободное вхождение пере менной x в формулу F не лежит в области действия никакого квантора по пере менной, входящей в терм t, то терм t называется свободным для переменной x в формуле F.

Примеры 1 Пусть F: = y Р(x)- формула;

t: = y – терм. Тогда терм t является несво бодным для переменной x в формуле F.

2 Терм f(x,z) свободен для переменной xв формуле yР(x,y)Q(x), но тот же терм f(x,z) не свободен для переменной x в формуле zy Р(x, y) Q (x).

11 Интерпретация исчисления предикатов 11.1 Интерпретация исчисления предикатов в алгебру высказываний Интерпретация ИП в алгебру высказываний определяется заданием мно жества M - области интерпретации и последующим приписыванием в качестве значений:

каждой предметной константе и каждой свободной переменной кон кретного элемента из M;


каждой n – местной предикатной или функциональной переменной конкретного n – местного предиката или соответственно функтора на M;

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

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

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

ложной – в противном случае.

Заметим, что истинностное значение формулы зависит от выбора множе ства M. Так, формула (x1Р(x1)x2Р(x2)) истинна во всех интерпретациях, где M - одноэлементное множество, и не во всех, в противном случае.

11.2 Равносильности Две формулы ИП называются равносильными, если они имеют одинако вые истинностные значения во всех интерпретациях. Запись: F = G («F равно сильно G»).

Имеет место следующие равносильности:

1) x F(x) = x F(x), x F(x)= x F(x);

2) x(F(x) G(x)) = xF (x) xG(x), x(F(x) G(x))=F(x) xG(x);

3)x y F(x, y) =y x F(x, y), x y F(x, y)= y x F(x, y);

4)x (F(x)С) = x F(x) С, x (F(x) С)= x F(x) С;

5)x (F(x)С) = x F(x) С, x (F(x) С) = x F(x) С;

6)С x F(x) = x ( С F(x)), С x F(x) = x (С F(x)).

Эти равносильности называются также законами логики предикатов. Фо рмула С не содержит вхождений переменной x.

Применяются, как и прежде. синтаксические сокращения: FG: = (F G) (G F), F G: = F С.

Раннее отмеченные законы F=F, (FС)=FG, (FG)= FG здесь тоже имеют место и используются.

С помощью равносильностей можно преобразовывать формулы.

12 Классификация формул логики предикатов 12.1 Тавтология. Противоречие. Выполнимая формула Формула ЛП называется тождественно истинной, или тавтологией, если она истинна в любой интерпретации.

Пример - Формула (x1 Р(x1) x2 Р(x2)) не является тавтологией.

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

Формула ЛП называется выполнимой, если она истинна хотя бы в одной интерпретации.

12.2 Логическое следствие. Логическая эквивалентность Формула ЛП G называется логическим следствием формулы F, если G истинна во всех интерпретациях, в которых F истинна. Запись: F G.

Имеют место логические следования:

7)x(F(x)G(x)) xF(x)xG(x), x F(x) xG(x)x(F(x)G(x)) ;

8) xF(x) H x(F(x) H), xF(x) H x(F(x) H), где формула Н не содержит вхождений переменной х.

Формулы F и G называются логически эквивалентными, если они явля ются логическими следствиями друг друга. Запись: F G.

12.3 Подстановка Пусть F(x) – формула, t – терм. Положим по определению F(t):= F(…x …) t//xТогда имеют место следующие теоремы.

Теорема 12.1 Формула xF(x)F(t),где t – терм, свободный для перемен ной x в формуле F, есть тавтология.

Теорема 12.2 Формула F(t) x F(x), где t – терм, свободный для пере менной x в формуле F, есть тавтология.

12.4 Предваренная нормальная форма В логике высказываний были введены нормальные формы – конъюнктив ная и дизъюнктивная. В логике предикатов первого порядка также имеется но рмальная форма, называемая предваренной нормальной формой (ПНФ).

Формула ЛП F называется находящейся в ПНФ, если она имеет вид:

Q1 x1 … Qn xn F0, (12.1) где Qi, i,= 1..n – один из кванторов (,), x i xj, если ij, F0 – формула, не имеющая кванторов.

Цепочка Q1 x1 … Qn xn называется предикатом, F0 – матрицей.

Пример - Формула xyz (Q(x,y) R(z)) находится в ПНФ.

Для любой формулы ЛП существует логически эквивалентная ей форму ла, находящаяся в ПНФ.

Приведение данной формулы ЛП к ПНФ можно произвести с помощью равносильностей (1-6) и следований (7-8).

Пример - Привести формулу x Р(x) x Q(x) к ПНФ.

Решение - x Р(x) x Q(x)= ((x Р(x)) x Q(x)= x ((x Р(x)) x Q(x)= x((Р(x)) Q(x)).

Следовательно, ПНФ для исходной формулы есть x(( Р(x)) Q(x)).

12.5 Скулемовская стандартная форма Доказательство теорем сопутствует основной задаче логики предикатов – описание всех тождественно – истинных формул. Согласно методу резолюций вместо доказательства тавтологичности формулы доказывается, что отрицание формулы противоречиво. Для этого формула приводится к скулемовской стан дартной форме, или стандартной форме. Ранее обсуждалось, как свести форму лу ЛП к ПНФ. Дальнейшее преобразование касается матрицы и префикса. Тех ника сведения бескванторной формулы (здесь - матрицы) к конъюнктивной нормальной форме также показана ранее. Теперь займемся элиминацией (уст ранением) кванторов.

Пусть формула F находится в предваренной нормальной форме Q1 x1 … Qn xn F0, где F0 есть конъюнктивная нормальная форма. Если Qr, 1 r n, есть квантор единичности в префиксе Q1x1…Qn xn, рассмотрим случаи:

1) никакой квантор общности не стоит в префиксе левее Qr. Тогда выби раем новую ( не встречавшуюся в формуле) константу с и заменяем все xr в F на с;

вычеркиваем Qr xr из префикса;

2) имеется непустой список Qr1, …, Qrm, 1 r1 …rm r, всех кванторов общности, встречающихся в префиксе левее Qr. Тогда выбираем новый ( не встречавшийся в формуле функциональный символ f, заменяем все xr в F0 на f(xr1, …, xrm).

Выполняем эту процедуру для всех кванторов существования в префиксе.

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

Пример – Указать ССФ формулы x y z uv w P(x,y,z,u,v, w).

Ответ - y zv P(x, y, z, f(y, z), v,g(y, z, v)).

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

Пример – Имеется формула x y z (( Р (x, y) Q (x, z)) R (x, y, z).

Ее ССФ может выглядеть так: x (( Р(x, f(x) ) R (x), g(x))) Q (x, g(x)) R (x, f(x), g(x)))), которую можно представить множеством Р (x, f(x)) R (x, f(x), g(x)), Q (x, g(x)) R (x, f(x), g(x)).

Следующая теорема – основа метода.

Теорема Пусть S – множество дизъюнктов, которые представляют стан дартную форму формулы F. Тогда F противоречива тогда и только тогда, ког да S противоречива.

13 Применения логики предикатов 13.1 Строение математических теорем Рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла». Предусловием этой теоремы являе тся предложение «Точка лежит на биссектрисе угла», а постусловием – пред ложение «Точка равноудалена от сторон угла». Оба условия являются предика тами. Обозначим их соответственно А(x) и В (x), xР, где Р –множество точек плоскости. Тогда рассматриваемая теорема состоит в том, что импликация пре дикатов А(x) В (x), то есть предикат «Если точка x лежит на биссектрисе угла, то она равноудалена от сторон этого угла», обращается в истинное выска зывание при всех x из множества Р. При помощи квантора общности это можно записать так:

x (А(x) В (x)), xР (13.1) Заметим, что словесная формулировка теоремы содержат описание мно жества объектов, о которых идет речь в теореме.

13.2 Методы доказательства теорем Приведем формулировку принципа математической индукции.

Пусть А(n) – произвольный предикат, заданный на множестве всех нату ральных чисел. Высказывание n А(n) истинно, если истинно высказывание А(1) (k) (А (k) А(k+1)). (Этот принцип, заметим, является одной из акси ом, определяющих натуральный ряд чисел).

Под методом математической индукции понимают следующий способ доказательства. Сначала проверяют истинность высказывания А(1). Затем, предположив истинность высказывания А(k), доказывают истинность высказы вания А (k+1). Если доказательство верно для любого натурального k, то в соо тветствии с принципом математической индукции высказывание А(n) признае тся истинным для всех n.

14 Свойства исчисления предикатов 14.1 Теорема Геделя о полноте исчисления предикатов Имеют место следующие метатеоремы.

Теорема 14.1 Всякая теорема классического исчисления предикатов пер вого порядка есть тавтология.

Теорема 14.2 Всякая тавтология является теоремой классического исчис ления предикатов первого порядка.

Вторая из этих теорем доказана К. Геделем (1930) и является утвержде нием о полноте классического исчисления предикатов первого порядка.

14.2 Непротиворечивость Теория К непротиворечива. Доказательство следует из теоремы 14.1 и аналогично доказательству о теории L.

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

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

15 Автоматическое доказательство теорем 15.1 Постановка задачи Алгоритм, проверяющий отношение Г T S, (15.1) называется автоматическим доказательством теорем (АДТ). Здесь - множест во посылок, S – заключение (формулы);

T-формальная теория, - знак выво димости В общем случае такого алгоритма не существует, то есть не существу ет алгоритма, который для любых S, Г, T выдавал бы ответ «Да», если выводи мость (15.1) имеет место, и ответ «Нет», в противном случае. В некоторых слу чаях подобные алгоритмы существуют. Например, в случае исчисления выска зываний. Поскольку в ИВ теоремами являются общезначимые формулы (и то лько они), то для проверки выводимости достаточно построить таблицы истин ности.


Частичным алгоритмом АДТ (из наиболее известных) является метод ре золюций (МР). Для любого прикладного ИП первого порядка МР дает ответ «Да», если (15.1) имеет место, и дает ответ «Нет» или не дает никакого ответа («зависает»), в противном случае. (Напомним, прикладное ИП есть ИП, которое содержит предметные константы и или функторы, иили предикаты и связы вающие их собственные аксиомы. ИП, не содержащее предметных констант, функторов, предикатов и собственных аксиом, называется чистым.) 15.2 Основа метода резолюций Теорема Если Г, S F, где F – тождественно ложная формула (проти воречие), то Г S.

Эта теорема лежит в основе МР, то есть используется идея «доказательс тва от противного».

В качестве противоречия принято использовать так называемую «пус тую» формулу и обозначать «пустым» квадратом:.

15.3 Правило резолюции Метод резолюций работает с предложениями. Напомним, предложение – бескванторная дизъюнкция литералов, а литералы – это формулы вида А, А, где А – атом. Далее будет показана методика перехода от формулы ИП к мно жеству предложений.

Правило резолюции для ИВ: пусть С1, С2 – предложения в ИВ, причем С = Р С1, С2 = Р С2, где Р – пропозициональная переменная, С1, С2 - пред C1, C ложения (в том числе, пустые);

тогда правило вывода Rназывается C1'C 2' правилом резолюции. Здесь С1, С2 – резольвируемые предложения;

С1С2 резольвента;

R – название правила;

Р, Р – контрарные литералы.

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

Правило резолюции для ИП: пусть С1, С2 – предложения в ИП, причем С = Р С1, С2 = Р С2, где P1, Р2 – литералы, имеющие наиболее общий унифи C1, C катор ;

тогда правило вывода R называется правилом резолюции.

C1'C 2' Здесь резольвента (С1С2) получена из предложения (С1С2) применением унификатора.

Напомним, формулы А (…, хi, …), В (…, хi, …) называются унифицируе мыми, если существует набор подстановок хi хii =1, в результате которых будет выполняться равенство А (…, хi, …) = В (…, хi, …). Указанный набор называется общим унификатором, наименьший набор из возможных называет ся наиболее общим унификатором (НОУ). В подстановках используются обоз начения хi – для переменных, хi – для формул, i =1 …n.

15.4 Метод резолюций Пусть требуется установить выводимость S G (15.2) Тогда предварительно формулы множества S и формула G независимо преобразуются в множества предложений. (Множество предложений есть кон ъюнкция предложений). В полученном множестве всех предложений С отыски вается резольвируемые предложения, к ним применяется правило резолюции, и резольвента добавляется в множество С. При повторных действиях возможны случаи:

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

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

3) Процесс продолжается, множество С пополняется, пустых предложе ний нет. Здесь не ясно.

Пример – Доказать теорему: L (((АВ) А) А) Решение: Проведем тождественные преобразования: (((АВ) А) А) = ( ( ( А В) А) А)= (((А В) А) А) = (А А) ( В А ) А.

Разбиваем на приложения и последовательно применяем правило резолюции:

1) А А 2) В А 3)..А 4) А (1, 3) 5) (3,4) Получена пустая формула. Теорема доказана.

15.5 Сведение формулы к множеству предложений Любая формула ИП может быть преобразована в множество предложений с помощью следующих замен ( - знак замены).

Элиминация импликации: АВ А В.

1) (Знак устранен).

Продвижение отрицания: А А, (А В) 2) А В, (А В) А В;

х А х А, х А х А. (Теперь знаки - только перед атомами.) 3) Разделение связанных переменных: Q1 х А (…Q2хВ (…х…) …) Q1 хА (…Q2 yВ(…y…)…), где Q1, Q2 – любые кванторы.

(Теперь нет случайно совпадающих связанных переменных.) Распространение кванторов: Q х А B Q х 4) (А В), Q х АВ Q х ( А В). (Теперь, после замен 1-4, формула находится в так называемой предваренной форме.) 5) Элиминация кванторов существования:

х1 Q2 х2 … Qn хn А (х1, х2, …, хn) Q2 х2… Qn хn А(а,х2,…, хn);

х1… х i-1 Q i+1 х i+1… Qn хn А (х1,…,xi,…xn) х1… х i-1 Q i+1 х i+1… Qn хn А (х1,…,f (х1, …, хi-1,… хn), где а – новая предметная константа, f – новый функтор, Q1, Q2,…, Qn – любые кванторы. (После замен 1-5 формула содержит кванторы только вида.) Элиминация кванторов всеобщности: х 6) А(х) А(х). (Теперь нет и кванторов.) 7) Приведение к КНФ:

А (ВС) (АВ) (А С), (АВ) С(А С) (В С). (Имеем КНФ после 1-7.) 8) Элиминация конъюнкции: АВ А,В. (Те перь, после замен 1-8, имеем множество предложений.) 15.6 Обоснование метода резолюций Теорема Если Г – множество предложений, полученных из формулы S, то S является противоречием тогда и только тогда, когда множество Г невыпол нимо.

Напомним, невыполнимость множества формул означает, что не сущест вует интерпретации, в которой все формулы множества имеют значение «исти на».

Пример – Даны высказывания F, G. Доказать, что F G.

F: = «Каждый, кто хранит деньги, получает проценты».

G:= «Если нет процентов, то никто не хранит деньги».

Решение Введем предикаты: М(х):= «х есть деньги»;

I(х):= «х есть проце нты»;

S (х,y): = «х хранит y»;

Е (х, y):= «х получает y». Перейдем к предложе ниям. При этом, очевидно, F=х (y (М(y) S(х, y)) z(I(z) Е (х, z)));

G = (х I(х)) (y z(М(y) S(z, y)))= х (I(х)) (y z (М(y) S(z, y)));

G=х ( I(х)) y z (М(y) S(z, y))= y zх ( I(х)) М(y) S(z, y)) z (I(z) М (а) S(b,а)), а/ y,b/ z.

Множество предложений:

1 ¬М(у) ¬S (х,y) I (f(х)), {F} 2 М(у) ¬S (х,y) Е (х, f(х)) { F} 3 ¬I(z) {G} 4 М(а) {G} 5 S (b,а) {G} Вывод:

6 ¬S (х,а) I (f(х)), (1,4), а/ y 7 I (f(b)), (5,6), b/х 8, (3,7) f(b)/ z Получена пустая формула. Выводимость доказана.

Пример – Даны высказывания: F1:= « Том не может быть хорошим студе нтом, если неверно, что он способный и отец помогает ему»;

F2 =«Том хороший студент только если его отец помогает ему». Доказать что F1F2.

Решение Пусть H(x) - «x-хороший студент» S(x)- «x-способный сту дент»;

Р (х, y) – «y помогает х». Тогда F1: = (S(а) Р (а,b)) (Н(а));

F2: = Р(аb) Н (а) Метод резолюций дает:

1 S(а) ¬Н (а) 2 Р (а, в) ¬Н (а) 3 ¬Р (а, в) 4 Н (а) 5 Выводимость доказана.

Задачи 1 Дать истинностную оценку высказываний:

а) В каждом ромбе диагонали взаимно перпендикулярны;

б) Число 3 есть делитель числа 19;

в) Число 1+28 – простое;

г) Картины Рериха загадочны;

д) Найдется число х, удовлетворяющее уравнению х2+1=0.

2 Из высказываний А:= «Испытания проведены», В:= «Программа выполнена» составьте высказывания:

а) АВ;

б) АВ;

в) АВ;

г) АВ.

3 Данные высказывания: х1:= «Идет дождь», х2:= «Очень жарко». За пишите символически составные высказывания:

а) Неверно, что идет дождь и очень жарко;

б) Если не идет дождь, то очень жарко.

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

а) Давление падает, и система не работает;

б) Вычисления выполнены точно или конструкция несовершенна;

в) Проект разработал Андрей или Петр, а эксперимент выполнил Иван;

г) Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси;

д) Программа будет выполнена если и только если материалы поступят своевременно;

е) Андрей помогает Петру или Петр помогает Петру, или они помогают друг другу.

5 Даны высказывания: А:= «Все кошки серы» и В:= «Число 6-простое число». Определите истинное значение высказываний:

а)¬A;

б)AВ;

в)¬АВ;

г) А¬В;

д) АВ;

е) В.

6 Составить таблицу истинности для высказываний;

а) ¬х1х2;

б)(ху)х;

в) ¬(ху);

г)(ху)(yz)(xz).

7 Проверьте с помощью таблицы тождества:

а) xy=¬xy б) x(xy)=x в) x¬xy=xy г)xyzxy¬zx¬y=x 8 Упростите следующее выражения:

а)¬xyzx¬y¬zxy¬z;

б)(xy)( ¬(xy) z)¬z(xy)(uv).

9 Составить нормальные формы для булевых функций:

а)y=x1x2;

б)y=x1/x2;

в)y=x1x2;

г) ¬(x(¬xz))(y¬z);

д) ¬(xy¬z)(xy);

е) (xy¬yz) ¬ (¬x u).

10 Выразить через,, операции:

а) ;

б) ;

с) ;

д).

11 Постройте переключательные схемы по формулам:

а) (х1 х2 ¬х3) (х1 х2 х3 х4);

б) (¬х1 (х2 ¬х3) ¬ х4) х1.

12 Запишите формулу, соответствующую переключательной схеме рису нка 16.1. Упростите эту формулу и постройте более простую схему:

А В С В А Рисунок 16. 13 Изобразите схематически множества истинности предикатов А(х), В(х) и покажите штриховкой множества истинности следующих предикатов:

а)¬А(х) ¬В(х);

б)¬ (А(х) В(х));

в) ¬А(х) ¬В(х);

г) ¬ (А(х) В(х)).

14 Контрольную работу, содержащую 3 задачи, выполняли 105 студентов.

Первую задачу решили 70 человек, вторую – 59, третью – 62. 90 студентов ре шили первую или вторую задачу, вторую или третью – 89, а первую или третью решили 91 студент. Сколько студентов решили все три задачи, если 6 студентов не решили ни одной задачи.

15 Пусть Е = е - множество европейцев. Рассматривается четыре пре диката:

А (е): = «Европеец – гражданин Швейцарии»;

В (е): = «Европеец владеет немецким языком»;

С (е): = «Европеец владеет французским языком»;

Д (е): = «Европеец владеет итальянским языком»;

Тогда что означает высказывание: е (А (е) В (е) С (е) Д (е)).

16 Рассмотрим два определения легкой контрольной:

1) Контрольная называется легкой, если каждую задачу решил хотя бы один студент.

2) Контрольная называется легкой, если хотя бы один ученик решил все задачи.

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

а) Может ли быть контрольная легкой в смысле первого определения и не легкой в смысле второго?

б) Может ли работа быть легкой в смысле второго определения и не лег кой в смысле первого.

17 Имеется два конечных числовых множества А и В и некоторые выска зывания о них:

1) Любое число из А больше любого числа из В;

2) Самое большое число из А больше самого большего числа из В;

3) Для любого числа из А найдется число из В, меньшее этого числа;

4) Каждое число из В меньше хотя бы одного числа из А;

5) Среднее арифметическое чисел из А больше среднего арифметиче ского чисел из В.

Найдите среди этих высказываний эквивалентные.

18 Граф G = (V, E) определяется заданием непустого множества вершин V, множества ребер Е и трехместного предиката Р(х,е,у): = «Ребро е соединяет вершины х и у», который определен на всех упорядоченных тройках (х,е,у), причем х,у V, е Е. Для орграфа х считается начальный, а у – конечный ве ршинами дуги е.

Запишите предикаты, задающие:

а)подмножество дуг орграфа, исходящих из вершины а;

б)подмножество дуг орграфа, входящих в вершину b;

в)подмножество ребер графа, инцидентных вершине а;

г)подмножество ребер графа, соединяющих вершины а и b.

19 В соответствии с определением графа в задаче 18 расшифруйте выска зывания:

а)ху ((ху) Р(х,е,у) Р (у,е,х));

б)х Р(х,е,х).

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

20 На множестве натуральных чисел определены предикаты: Р(х):= «Чис ло х делится на 8» и Q(x): = «х – четное число»

Прочитайте следующие высказывания и выясните, какие из них истинны:

а) х Р(х);

б) х Р(х);

в) х Q(x);

г) х ¬Q(x);

д) х ¬Q(x);

е) х (Р(х) Q(x));

з) х (Q(x) Р(х)).

21 Пусть х – множество прямых на плоскости. На этом множестве опре делены предикаты: R (х,у): = «Прямая х пересекается с прямой у», S(х,у):= «Прямая х параллельна прямой у», причем х,у Х.

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

а) х у R(х,у);

б) ху ¬S (х,у));

в) ху (R (х,у) ¬S (х,у));

г) ху (R (х,у) S (х,у)).

22 На множестве натуральных чисел определены предикаты: Р(х):= «х – простое число», Q(x): = «х - четное число», R (х,у): = « х- не равно у». Переве дите на русский язык высказывание:

х (Р(х) Q(x)) ¬х (Р(х) Q(x) у (R (х,у) Р(у) Q(у))).

23 Запишите предикаты для высказываний:

а) Каждый студент изучает (один язык) или английский, или немецкий, или французский язык;

б) Некоторые устройства укомплектованы осциллографами;

в) Не все телевизоры работают хорошо;

г) Ни один прибор не оказался забракованным.

24 Установите истинностное значение предикатов:

а) Если некоторые транзисторы негодные и все транзисторы проверяются, то среди проверенных транзисторов найдутся негодные;

б) Никто из спортсменов не изучает иностранных языков, если все инже неры изучают иностранный язык и некоторые из них – спортсмены.

25 Дан предикат х (Р(х,у,z) у Q(x,у)) Q(x,у) ¬S. Здесь Р(х,у,z) – трехместный, Q(x,у) – двухместный, S – нульместный предикат. Требуется определить истинностное значение данного предиката при условиях: М = а, в, S = 0;

х=b, у=а, z=а;

предикаты Р, Q имеют таблицу 1:

xуz Р (х, у, z) Q(x, у) ааа 0 ааb аbа 1 аbb bаа 0 bаb bbа 0 bbb в) L¬А (АВ);

г) L (¬В ¬А) (А В);

д) L(АВ) (¬В ¬А);

е) LА(¬В ¬(АВ)) 27 В теории L доказать выводимость:

а) АВ, ВС, А С;

б) АВ, В С А С;

в) D, АВ, D С, С В, А С;

г) РQ R, Q P, Q R.

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

а) Для того, чтобы матрица имела обратную, достаточно, чтобы ее опре делить был равен нулю.

б) Для того, чтобы определитель матрицы был отличен от нуля, достаточ но, чтобы эта матрица имела обратную.

в) Для того, чтобы определитель матрицы был равен нулю, необходимо, чтобы эта матрица не имела обратной.

г) Матрица имеет обратную тогда и только тогда, когда её определитель не равен нулю.

29 Докажите логическое следствие (Р Q) (R S) (S Q T) T ¬ P R через соответствующую тавтологию;

с помощью правил вывода;

де дуктивным способом.

30 Докажите равносильность высказываний Х (Х ¬ (Y Z)) и ¬X ¬Y Z. Представьте эту равносильность в виде логических следствий.

31 Упростите следующую систему высказываний: А (В С);

В ¬ (А С);

С (А В);

А (В С);

¬A¬CB;

А В С. Приняв для А, В, С не которые высказывания, сформулируйте сложное высказывание исходной и упрощенной систем.

32 Исследуйте каждую из приведенных ниже систем высказываний на противоречивость:

а) А ¬В ¬С;

(D Е) F;

F¬ (G H);

¬С Е F;

б) (А В) С D;

D Е F;

А ¬F;

в) (А В) (С D);

(В D) (¬С А);

(Е F) (F ¬ D);

¬ Е Е;

г) (А В С) (D В Е);

(F А) G Н;

(G Н) F D;

¬(С Е);

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

33 Запишите в символической форме и установите логичность следую щих рассуждений:

а) Если заменить лампу (А), телевизор будет работать (В) при условии, что напряжение подключено (С). Лампа заменена, а напряжение не подключе но. Следовательно, телевизор не будет работать.

б) Если поднять давление (А) или увеличить температуру (В), то реакция произойдет быстрее (С), но опасность повысится (Д). Если опасность повысит ся, то необходимо принять меры защиты (Е). Меры защиты не приняты. Следо вательно, давление поднимать нельзя.

в) Если упростить схему (А), стоимость снизится (В), и если применить новые элементы (С), надежность увеличится (Д). Можно или упростить схему, или применить новые элементы. Однако, если упростить схему, то надежность не увеличится, а если применить новые элементы, то стоимость не снизится.

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

34 Свободен ли терм f (х1,х2) для х1 в формулах А1 (х1,х2) х2 А (х2), х2А(х2,а1)) х2А(х1,х2)?

35 Указать свободные и связанные вхождения переменных в следующие формулы:

х3 (х1А (х1,х2) А (х3,х1));

1) х2А (х3,х2) х3А(х3,х2);

2) (х2 х1А1 (х1,х2, f1 (х1,х2))) х1А2 (х2, f2(х1)).

3) 36 Даны формулы:

1) А1^2 (f1^2 (x1,x2),a1);

А1^2 (x1,x2) А1^2 (x2,x1);

2) х1 х2 х3 (А1^2 (x1,x2) А1^2 (x2,x3) А1^2 (x1,x3).

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

а) Область интерпретации – множество всех целых положительных чисел;

А1 (y,z), f12(x,z), a1 интерпретируется соответственно как y z, yz, 1.

б) Область интерпретации – множество всех множеств целых чисел, А (y, z), f12(y, z), а1 интерпретируются соответственно как yz, z y, (пустое множество).

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

а) ((х1А11(х1) х 1А21(х1)) ((х1(А11(х1) А21(х1)));

б) (х1(А11(х1) А21(х1))) ((х1 А11(х1)) (х1 А21(х1))).

38 Показать, что следующие формулы логически общезначимы:

а) хi хj F хj хi F;

б) хi хj F хj хi F;

в) хi F хi F;

г) хi F хi F.

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

а) Для любого множества х существует множество у такое, что мощность у больше мощности х. Если х включено в у, то мощность х не больше мощнос ти у. Всякое множество включено в V. Следовательно, V – не множество.

б) Если всякий предок предка данного индивидуума есть также предок того же индивидуума, и никакой индивидуум не есть предок самого себя, то должен существовать некто, не имеющий предков.

40 Даны высказывания:

F: = «Каждый, кто хранит деньги, получает проценты»;

G: = «Если нет процентов, то никто не хранит денег»

Доказать: F G.

41Записать в виде категорических высказываний:

а) «Не все телевизоры работают хорошо»;

б) «Ни один прибор не оказался забракованным».

42Имеются посылки:

F1: = «Таможенные чиновники обыскивают каждого, кто въезжает в страну, кроме высокопоставленных лиц», F2: = «Некоторые люди, способствующие провозу наркотиков, въезжали в страну и были обысканы исключительно людьми, способствующими провозу наркотиков»;

F3: = «Никто из высокопоставленных лиц не способствовал провозу нар котиков».

Предполагаемое заключение G: = «Некоторые из таможенников способс твовали провозу наркотиков. Доказать: F1, F2, F3 G.

Указание - Применить метод резолюций.

43 Король думает, что королева думает, что она не в своем уме. В своем ли уме король?

44 Посылка: «Студенты – граждане». Заключение: «Голоса студентов – голоса граждан». Вывести методом резолюций.

45 Пусть F1 и F2 таковы:

F1: х (Р(х)Q(x)), F2: Q(a).

Доказать, что Р (а) есть логическое следствие F1 и F2.

46 Восстановить скобки в выражениях:

а) х2 А11(х1) А23(х1,х2,х3) х1 А21(х1);

б) х1 А11(х1) х2 А21(х2) А12(х1,х2) А11 (х2).

47 Перевести следующие предложения на язык формул:



Pages:   || 2 | 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.