Министерство образования и науки РФ

Министерство образования и науки РФ

Рязанский государственный университет имени С.А. Есенина

Исследовательская работа по математической логике

«Равносильность формул логики высказываний. Равносильные преобразования.»

Выполнила

студентка 2 курса группы 3108

физико-математического факультета

Бакина Юлия

Проверила: Солонина А.Г.

Рязань 2013

Содержание

Введение............................................2

Цели работы и задачи................................ 3

1. Определение равносильных формул.................4

2. Важнейшие равносильности алгебры логики.........5

3. Некоторые из важнейших равносильностей алгебры

другими словами..................................8

4. Равносильные преобразования..................... 9

5.Принцип двойственности...........................10

Заключение........................................ 11

Список использованной литературы...................12

Введение

Логика (др. греч. λογική — «наука о рассуждении», «искусство рассуждения» от λόγος — «речь», «рассуждение», «мысль») — это наука о формах, методах и законах интеллектуальной познавательной деятельности, формализуемых с помощью логического языка. Логика состоит из большого числа логических систем. Эти системы принято делить на классическую логику, включающую классические логику высказываний и логику предикатов, и неклассическую логику.

Как самостоятельная наука логика сложилась в IV в. до н.э. Ее основателем по праву считается древнегреческий философ Аристотель (384-322 гг до н.э.).В своих научных трудах Аристотель впервые дал ее систематическое изложение и назвал “традиционной” формальной логикой. Основным содержанием аристотелевской логики является теория дедукции, но в его трудах также прослеживаются начала исчисления высказываний.
Логика высказываний - раздел логики, в котором вопрос об истинности или ложности высказываний решается на основе изучения способа построения высказываний из элементарных (далее не разлагаемых и не анализируемых) с помощью логических связок. Логику высказываний называют также исчислением высказываний. Высказыванием называется всякое утверждение (повествовательное предложение), про которое всегда определенно и объективно можно сказать, является ли оно истинным или ложным.

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

Цель работы:

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

Задачи:

-выяснить, что такое равносильные формулы и преобразования;

-рассмотреть важнейшие равносильности алгебры логики;

-применить равносильные преобразования на практике.

1.Определение равносильных формул

В пособии Л.В. Балабко «Алгебра логики» определение выглядит так:

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

Равносильность формул будем обозначать знаком º, а запись А º В означает, что формулы А и В рав­носильны.

В учебнике И.Л. Никольской «Математическая логика» определение излагается следующим образом:

Определение. Формулы F1 и F2 называются равносильными, если их эквиваленция F1↔ F2 является тавтологией.

Эквиваленция истинна тогда и только тогда, когда составляющие её высказывания оба истинны либо оба ложны; следовательно, F1↔ F2 есть тавтология только в том случае, если формулы F1 и F2 «одновременно», т.е. при одинаковых наборах значений переменных, входящих в формулы, принимают одинаковые значения.

2. Важнейшие равносильности алгебры логики

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

I группа. Основные равносильности.

1) x Щ x є x; x Ъ x є x – законы идемпотентности;

2) x Щ 1 є x; x Ъ 1 є 1;

3) x Щ 0 є 0; x Ъ 0 є x;

4) xє x – закон тождества;

x Щ` є 0 – закон противоречия;

x Ъ` є 1 – закон исключения третьего;

5) є x – закон снятия двойного отрицания;

6) x Щ (x Ъ y) є x; x Ъ (x Щ y) є x – законы поглощения.

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

х	у	уvx	хЩ(уvx)

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

II группа. Равносильности, выражающие одни логические операции через другие.

1) x ® y є` Ъ y;

2) x «y є (x ® y) Щ (y ® x);

3) Закон де Моргана (закон инверсии или отрицания):

4) и 5) тождества докажем, применив закон двойного отрицания и тождества 3) второй группы:

III группа. Основные законы алгебры логики.

1) коммутативность:

x Щ y є y Щ x,

x Ú y º y Ú x;

2) ассоциативность:

x Щ (y Щ z) є (x Щ y) Щ z

x Ъ (y Ъ z) є (x Ъ y) Ъ z

3) дистрибутивность:

x Щ (y v z) є x Щ y Ъ x Щ z – относительно дизъюнкции,

x Ъ (y Щ z) є (x Ъ y) Щ (x Ъ z) – относительно конъюнкции.

Докажем справедливость дистрибутивности относительно конъюнкции. Составим таблицу истинности, которая содержит 2³ = 8 строк:

х	у	z	yz	x v yz	x v y	x v z	(x v y)(x v z)

3.Некоторые из важнейших равносильностей алгебры другими словами.

Многие законы из основных равносильностей в математическо-логической форме выражают основные законы формальной логики, сформулированные ещё Аристотелем.

З а к о н т о ж д е с т в а (xє x) утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. З а к о н п р о т и в о р е ч и я (x Щ` є 0) говорит о том, что никакое предложение не может быть истинным одновременно со своим отрицанием. З а к о н и с к л ю ч е н и я т р е т ь е г о (x Ъ` є 1) показывает нам, что для каждого высказывания имеется лишь 2 логические возможности: это высказывание истинно или ложно, третьего не дано. Согласно з а к о н у с н я т и я д в о й н о г о о т р и ц а н и я ( є x), отрицать отрицание какого-либо высказывания – то же, что и утверждать это высказывание. Например, высказывание «Неверно, что 2 на 2 НЕ равно 4» означает то же, что и «2 на 2 равно 4».

А з а к о н ы к о м м у т а т и в н о с т и и а с с о ц и а т и в н о с т и конъюнкции и дизъюнкции аналогичны одноименным законам сложения и умножения чисел. Иногда дизъюнкцию так и называют логическим сложением, а конъюнкцию - логическим умножением.

В силу з а к о н о в и д е м п о т е н т н о с т и в алгебре логики нет «показателей степеней» и «коэффициентов»: конъюнкция одинаковых «сомножителей» равносильна одному из них; и дизъюнкция одинаковых «слагаемых» равносильна одному из них.

4.Равносильные преобразования.

Используя равносильности I, II и III групп можно часть формулы или формулу заменить равносильной ей формулой.

Такие преобразования формул называются равносильными.

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

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

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

Доказать равносильность . Используя равносильности I, II и III групп запишем цепочку равносильных формул:

*здесь знаком & обозначается конъюнкция (Щ)

5.Принцип двойственности.

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

1) x Щ x є x; x Ъ x є x – законы идемпотентности;

2) коммутативность:

x Щ y є y Щ x, x Ú y º y Ú x;

3) ассоциативность:

x Щ (y Щ z) є (x Щ y) Щ z, x Ъ (y Ъ z) є (x Ъ y) Ъ z

4) дистрибутивность:

x Щ (y v z) є x Щ y Ъ x Щ z, x Ъ (y Щ z) є (x Ъ y) Щ (x Ъ z) 5)

6) закон де Моргана (закон инверсии или отрицания):

В этих соответствиях проявляется так называемый принцип двойственности. Две формулы, не содержащие знаков ® и «,называются двойственными, если каждую из них можно получить из другой заменой Щ,Ъ,1,0 соответственно на Ъ,Щ,0,1.

Принцип двойственности утверждает: если 2 формулы, не содержащие знаков ® и «равносильны, то двойственные им формулы тоже равносильны.

Например, для формулы 0 двойственной является формула 1, а для формулы хЩ0- формула хЪ1; убедившись, что хЩ0є0, согласно принципу двойственности получаем равносильность хЪ1є1.

Заключение

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

По критерию научности источники не отличаются, оба автора дали верные определения.

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

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

1. Никольская И.Л. Математическая логика — М.: Высшая школа, 1981.

2. Балабко Л.В Алгебра логики – Архангельск: Северный федеральный университет имени М.В.Ломоносова,2011.

3. Игошин В.И. Математическая логика и теория алгоритмов - М.: Академия, 2007.

4. Лихтарников Л.М. Курс лекций по математической логике - СПб.:Лань, 1999.

5. Клини С. Математическая логика - М.: 1973.

Дата добавления: 2015-09-30