Применение аппарата алгебры логики к решению содержательных задач

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Основные понятия

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

Булевы функции

Выражение одних булевых функций через другие

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

3. Некоторые законы логики высказываний

Глава 2. Применение аппарата алгебры логики к решению содержательных задач

1. Перевод выражений естественного языка на символический язык алгебры логики

2. Примеры перевода высказываний естественного языка на язык алгебры логики

3. Простейшие задачи

4. Парадоксы

Заключение

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

Введение

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

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

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

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

Элементы математической логики можно найти уже в работах древнегреческих философов. Аристотель считал, что с помощью логики можно ответить на вопрос «Что есть истина?». Собрание его поучений, известное как Органон (датируемое IV в. до н.э.), - самое раннее подробное произведение о логике. Для древних греков логика была средством для анализа языка в поисках истины и потому считалась отраслью философии. В основе Аристотелевой логики лежит силлогизм (силлогизм - это дедуктивное умозаключение, в котором одно суждение является необходимым следствием двух других). Самый известный силлогизм (кстати, в трудах Аристотеля его нет) звучит так:

Все люди смертны;

Сократ -- человек;

Следовательно, Сократ смертен.

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

Смертность Сократа и без силлогизма достаточно очевидна, но приведенным выше примером круг силлогизмов не ограничен. Интересны, например, следующие две посылки, предложенные математиком XIX века Чарльзом Доджсоном, носившем также псевдоним Льюис Кэрролл:

Все философы логичны;

Нелогичный человек всегда упрям.

Из этой пары вывести верное заключение уже не так просто. Кстати, звучит оно так: «Некоторые упрямые люди не являются философами» (заметьте, что в заключении появилась неопределенность, выраженная словом «некоторые»).

В течение двух тысяч лет математики сражались с логикой Аристотеля, пытаясь обуздать ее математическими символами и операторами. До XIX в. подойти близко к решению этой проблемы удалось лишь Готфриду Вильгельму Лейбницу (1648-1716), который в начале своей научной деятельности занимался логикой, но затем заинтересовался другими проблемами (например, независимо от Ньютона и одновременно с ним изобрел дифференциальное исчисление). Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определённых действий по установленным правилам.

А затем наступило время Джорджа Буля.

Джордж Буль (George Boole) появился на свет в Англии в 1815 г. Шансы на успех в жизни у него были весьма невелики. Он родился в семье башмачника и бывшей горничной, и жесткая классовая структура Британии предполагала, что сам он также не достигнет больших высот. Но благодаря своему пытливому уму и помощи отца (серьезно увлекавшегося математикой и литературой), юный Джордж преуспел в науках, которые считались привилегией мальчиков из высших классов, в том числе в латыни, греческом и математике. Написав несколько научных статей по математике, в 1849 г. Буль стал первым профессором математики Колледжа Королевы в ирландском городе Корк.

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

Однако как самостоятельный раздел математики математическая логика начала формироваться только с середины XIX в.

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

Глава 1. Основные понятия

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

Логическое высказывание - это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Так, например, предложение «8 - четное число» следует считать высказыванием, так как оно истинное. Предложение «Париж - столица Германии» тоже высказывание, так как оно ложное.

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

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

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

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

3. Закон исключенного третьего: каждое высказывание непременно должно быть либо истинным, либо ложным. Это требование основано на убеждении, что относительно любого осмысленного высказывания всегда может быть установлено, истинно оно или ложно. А значит, что третьего не дано.

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

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения - является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание «площадь поверхности Индийского океана равна 75 млн км2» в одной ситуации можно посчитать ложным, а в другой - истинным. Ложным - так как указанное значение неточное и вообще не является постоянным. Истинным - если рассматривать его как некоторое приближение, приемлемое на практике.

Употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если ..., то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Так, например, из элементарных высказываний «Петров - врач», «Петров - шахматист» при помощи связки «и» можно получить составное высказывание «Петров - врач и шахматист», понимаемое как «Петров - врач, хорошо играющий в шахматы».

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание «Петров - врач», а через В - высказывание «Петров - шахматист». Тогда составное высказывание «Петров - и врач, и шахматист» можно кратко записать как А и В. Здесь «и» - логическая связка, А, В - логические переменные, которые могут принимать только два значения - «истина» или «ложь», будем обозначать их соответственно «1» и «0».

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

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

Булевы функции

· Отрицание (отрицание - то, что отрицает собой что-нибудь; отрицать - отвергать существование, необходимость, обязательность чего-либо) - операция, выражаемая словом «не» - обозначается знаком , ¬ или чертой над высказыванием (). Будем обозначать его чертой над высказыванием .

Высказывание истинно, когда А ложно. И ложно, когда А истинно.

А
1 0	0 1

А
«Петров - врач»	«Петров не врач»

· Конъюнкция (лат. conjunctio - соединение) или логическое умножение - операция, выражаемая связкой «и» - обозначается точкой , знаками , &. Будем обозначать ее точкой .

Высказывание А*В истинно, когда оба высказывания истинны. И А*В ложно, когда: 1) А истинно, В ложно; 2) А ложно, В истинно; 3) А ложно и В ложно.

А	В	А*В
1 1 0 0	1 0 1 0	1 0 0 0

А	В	А*В
«Петров - врач»	«Петров - шахматист»	«Петров - врач и шахматист»

· Дизъюнкция (лат. disjunctio - разделение) или логическое сложение - операция, выражаемая связкой «или» - обозначается знаком

Размещено на http://www.allbest.ru/

или плюсом (+). Будем обозначать ее

Размещено на http://www.allbest.ru/

.

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

Размещено на http://www.allbest.ru/

В ложно, когда оба высказывания ложны. И А

Размещено на http://www.allbest.ru/

В истинно, когда хоть одно из них истинно.

А

А

В

Размещено на http://www.allbest.ru/

1 1 0 0	1 0 1 0	1 1 1 0

А

А

В

Размещено на http://www.allbest.ru/

«Петров - врач»	«Петров - шахматист»	«Петров - или только врач, или только шахматист или и врач, и шахматист одновременно»

Исключающая дизъюнкция - операция, выражаемая «либо …, либо …» - обозначается .

А	В	АВ
1 1 0 0	1 0 1 0	0 1 1 0

А	В	АВ
«Петров - врач»	«Петров - шахматист»	«Петров только врач или только шахматист»

· Импликация (лат. implico - тесно связаны) - операция, выражаемая связками «если …, то …», «из … следует …», «… влечет …» - обозначается знаком >.

Высказывание А>В ложно, когда А истинно, В ложно. И А>В истинно, когда: 1) А истинно и В истинно; 2) А ложно и В истинно; 3) А ложно и В ложно.

А	В	А>В
1 1 0 0	1 0 1 0	1 0 1 1

А	В	А>В
«Петров - стоматолог»	«Петров - врач»	«если Петров - стоматолог, то он врач»

· Эквиваленция или двойная импликация - операция, выражаемая связками «… тогда и только тогда, когда …», «… необходимо и достаточно …», «… равносильно …» - обозначается знаком -, = или ?. Будем обозначать ее -.

Высказывание А-В истинно, когда значения А и В совпадают и ложно, когда: 1) А истинно, В ложно; 2) А ложно, В истинно.

А	В	А-В
1 1 0 0	1 0 1 0	1 0 0 1

А	В	А-В
«Петров - стоматолог»	«Петров - врач»	«Петров - стоматолог тогда и только тогда, когда он врач»

· Штрих Шеффера - операция, выражаемая «неверно, что …, или неверно, что …» - обозначается ¦. Высказывание А¦В ложно, когда А и В истинны, и истинно, когда 1) А истинно, В ложно; 2) А ложно, В истинно; 3) А и В ложны.

А	В	А¦В
1 1 0 0	1 0 1 0	0 1 1 1

А	В	А¦В
«Петров - врач»	«Петров - шахматист»	«Неверно, что Петров - врач, или неверно, что Петров - шахматист»

· Стрелка Пирса - операция, выражаемая «неверно, что …, и неверно, что …» - обозначается v. Высказывание АvВ истинно, когда А и В ложны, и ложно, когда: 1) А и В истинны; 2) А истинно, В ложно; 3) А ложно, В истинно.

А	В	АvВ
1 1 0 0	1 0 1 0	0 0 0 1

А	В	АvВ
«Петров - врач»	«Петров - шахматист»	«Неверно, что Петров - врач, и неверно, что Петров - шахматист»

Существует еще одна булева функции, которая не имеет общепринятого названия и обозначения:

· «неверно, что из … следует …»

А	В
1 1 0 0	1 0 1 0	0 1 0 0

А	В
«Петров - стоматолог»	«Петров - врач»	«Неверно, что из того, что Петров - стоматолог, следует, что Петров - врач»

Выражение одних булевых функций через другие

Импликацию можно выразить через дизъюнкцию и отрицание:

А>В=

Размещено на http://www.allbest.ru/

В

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А-В=

Размещено на http://www.allbest.ru/

В)*(

Размещено на http://www.allbest.ru/

А)

А-В=(А*В)

Размещено на http://www.allbest.ru/

( *)

Исключающую дизъюнкцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

АВ=(А*)

Размещено на http://www.allbest.ru/

(*В)

Штрих Шеффера можно выразить через отрицание и дизъюнкцию:

А¦В=

Размещено на http://www.allbest.ru/

Стрелку Пирса можно выразить через отрицание и конъюнкцию:

АvВ=*

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

1). Отрицание

2). Конъюнкция

3). Дизъюнкция

4). Импликация

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

Лат. propositio - предложение

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

2. Если А - пропозициональная формула, то - тоже пропозициональная формула.

3. Если А и В - пропозициональные формулы, то выражения (А*В), (А

Размещено на http://www.allbest.ru/

В), (АВ), (А>В), (А-В), (А¦В), (АvВ) - тоже пропозициональные формулы.

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

Выполнимые формулы - это формулы, которые при определенных сочетаниях переменных принимают значение «истина», а при некоторых других сочетаниях принимают значение «ложь».

Тождественно-истинные формулы (тавтологии) - формулы, принимающие значение «истина» при любых значениях истинности входящих в них переменных.

3. Некоторые законы логики высказываний

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

Закон двойного отрицания: Если неверно, что неверно А, то А истинно ().

Закон тройного отрицания: Если неверно, что неверно, что неверно А, то А ложно ().

Закон контрапозиции: Если из А следует В и неверно, что В, то неверно, что А ().

Закон приведения к абсурду: Если из А следует, что верно В и неверно В, то А ложно ().

x

Закон	Для ИЛИ (дизъюнкция)	Для И (конъюнкция)
	Переместительный

Размещено на http://www.allbest.ru/

y=y

Размещено на http://www.allbest.ru/

x

x*y=y*x
	Сочетательный

Размещено на http://www.allbest.ru/

(y

Размещено на http://www.allbest.ru/

z)=(x

Размещено на http://www.allbest.ru/

y)

Размещено на http://www.allbest.ru/

x*(y

(x*y)*z=x*(y*z)
	Распределительный

Размещено на http://www.allbest.ru/

z)=x*y

Размещено на http://www.allbest.ru/

x

Размещено на http://www.allbest.ru/

y*z=(x

Размещено на http://www.allbest.ru/

y)*(x

Размещено на http://www.allbest.ru/

	Правила де Моргана

Размещено на http://www.allbest.ru/

x

	Идемпотенции

Размещено на http://www.allbest.ru/

x

x*x=x
	Поглощения

Размещено на http://www.allbest.ru/

x*(x

Размещено на http://www.allbest.ru/

(x*y)

	Склеивания

Размещено на http://www.allbest.ru/

(

(x

*y)=y

Размещено на http://www.allbest.ru/

y)*(

Размещено на http://www.allbest.ru/

x

	Операция переменной с ее инверсией

Размещено на http://www.allbest.ru/

x

=1	x*=0
	Операция с константами

Размещено на http://www.allbest.ru/

0=x; x

Размещено на http://www.allbest.ru/

x*1=x; x*0=0
Двойного отрицания

Глава 2. Применение аппарата алгебры логики к решению содержательных задач

логический высказывание булевой пропозициональный алгебра

1. Перевод выражений естественного языка на символический язык алгебры логики

А

Форма высказывания естественного языка	Соответствующая формула языка алгебры логики
Не А; неверно, что А; А не имеет места
А и В; как А, так и В; не только А, но и В; А вместе с В; А, несмотря на В; А в то время как В	А*В
А, но не В; не В, а А	А*
	А или В; А, или В, или оба

Размещено на http://www.allbest.ru/

(А*)

	Либо А, либо В; не А, разве что не В; либо не А, либо не В; А или В, но не оба

Размещено на http://www.allbest.ru/

(

*В)
	Либо А, либо В и С; А, разве что В и С

Размещено на http://www.allbest.ru/

	Либо А и В, либо С и D

Размещено на http://www.allbest.ru/

Если А, то В; В, если А; А только, если В; А только тогда, когда В; А достаточно для В; А только при условии что В; В необходимо для А; А, значит В; для В достаточно А; А влечет В; для А необходимо В; из А следует В; В тогда, когда А	А>В
А эквивалентно В; А тогда и только тогда, когда В; А если и только если В; А необходимо и достаточно для В	А-В

2. Примеры перевода высказываний естественного языка на язык алгебры логики

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

1) Если светит солнце, то для того, чтобы не было дождя, достаточно, чтобы дул ветер.

Обозначим:

Солнечная погода - С

Идет дождь - Д

Дует ветер - В

Обратившись в вышеприведенную таблицу, составим формулу:

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

Обозначим:

Солнечная погода - С

Идет дождь - Д

Дует ветер - В

Пасмурная погода - П

3) Погода не только солнечная, но и безветренная. Значит, дождя не будет, если не поднимется ветер.

Обозначим:

Солнечная погода - С

Идет дождь - Д

Дует ветер - В

Теперь более сложные:

Найдем отрицания следующих высказываний:

1) Петя будет купаться только при солнечной погоде, если будет жарко.

Обозначим:

Коля будет купаться - К

Солнечная погода - С

Будет жарко - Ж

2) В кино пойдет либо Коля, либо Петя.

Обозначим:

Коля идет в кино - К

Петя идет в кино - П

3) Если урок будет интересным, никто из мальчиков - Петя, Ваня, Коля - не будет смотреть в окно.

Урок будет интересным - И,

Петя будет смотреть в окно - П,

Ваня будет смотреть в окно - В,

Коля будет смотреть в окно - К,

3. Простейшие задачи

Рассмотрим решение довольно простых задач:

1) На вопрос, какая погода будет завтра, синоптик ответил:

1. Если будет мороз, то снег выпадет только при пасмурной погоде.

2. Если не будет мороза, но пойдет снег, то погода будет пасмурной.

3. Не будет ни снега, ни дождя, если небо будет ясным.

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

Какую погоду предсказал синоптик?

Решение

Обозначим:

Мороз - М,

Снег - С,

Пасмурная погода - П (ясная погода - ),

Дождь - Д.

Запишем высказывания синоптика:

1.

2.

3.

4.

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

1.

М	С	П	С>П	М>(С>П)
1	1	1	1	1
1	1	0	0	0
1	0	0	1	1
0	0	0	1	1
0	1	1	1	1
0	0	1	1	1
1	0	1	1	1
0	1	0	0	1

2.

М	С	П			>П
1	1	1	0	0	1
1	1	0	0	0	1
1	0	0	0	0	1
0	0	0	1	0	1
0	1	1	1	1	1
0	0	1	1	0	1
1	0	1	0	0	1
0	1	0	1	1	0

3.

П	С	Д				?
1	1	1	0	0	0	0	1
1	1	0	0	0	1	0	1
1	0	0	0	1	1	1	1
0	0	0	1	1	1	1	1
0	0	1	1	1	0	0	0
0	1	1	1	0	0	0	0
1	0	1	0	1	0	0	1
0	1	0	1	0	1	0	0

4.

С

М

С

П

Д

Размещено на http://www.allbest.ru/

П> С

Размещено на http://www.allbest.ru/

>(П>С

Размещено на http://www.allbest.ru/

1	1	1	1	0	1	1	1	0
1	1	1	0	0	1	1	1	0
1	1	0	0	0	1	1	1	0
1	0	0	0	0	0	1	1	0
0	0	0	0	1	0	1	1	0
0	1	1	1	1	1	1	1	0
0	0	1	1	1	1	1	1	0
0	0	0	1	1	1	1	1	0
0	1	1	0	1	1	1	1	0
0	1	0	0	1	1	1	1	0
0	0	1	0	1	0	0	0	1
1	0	0	1	0	1	1	1	0
1	0	1	0	0	1	1	1	0
0	1	0	1	1	1	1	1	0
1	0	1	1	0	1	1	0	1
1	1	0	1	0	1	1	0	1

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

М - ложь,

С - ложь,

П - истина,

Д - ложь.

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

2) Внимание Андрея, Дениса и Марата привлек промчавшийся мимо них автомобиль.

- Это английская машина марки «Феррари», - сказал Андрей.

- Нет, машина итальянская марки «Понтиак», - возразил Денис.

- Это «Сааб», и сделан он не в Англии, - сказал Марат.

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

Какой марки этот автомобиль и в какой стране он сделан?

Решение

Обозначим:

Машина английская - А,

«Феррари» - Ф,

Машина итальянская - И,

«Понтиак» - П,

«Сааб» - С.

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

1.

Размещено на http://www.allbest.ru/

2.

Размещено на http://www.allbest.ru/

3.

Размещено на http://www.allbest.ru/

Соединим все эти высказывания конъюнкцией (и):

(

Размещено на http://www.allbest.ru/

)?(

Размещено на http://www.allbest.ru/

)?(

Размещено на http://www.allbest.ru/

).

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

(

Размещено на http://www.allbest.ru/

)?(

Размещено на http://www.allbest.ru/

)?(

Размещено на http://www.allbest.ru/

)=

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

=0

Размещено на http://www.allbest.ru/

0

Размещено на http://www.allbest.ru/

0

Размещено на http://www.allbest.ru/

0

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

0

Размещено на http://www.allbest.ru/

0

Размещено на http://www.allbest.ru/

0=

Высказывание истинно только при И=1, Ф=1, А=0, П=0, С=0.

Ответ: машина итальянская марки «Феррари».

3) В симфонический оркестр приняли на работу трех музыкантов - Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что:

1. Смит самый высокий;

2. играющий на скрипке меньше ростом играющего на флейте;

3. играющие на скрипке и флейте и Браун любят пиццу;

4. когда между альтистом и трубачом возникает ссора, Смит мирит их;

5. Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение

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

Составим таблицу соответствий людей и музыкальных инструментов.

	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун
Смит
Вессон

Заполнять ее будем символами «1», «0», соответственно «истина» и «ложь».

Из 1 и 2 условий следует, что Смит не играет на скрипке (он не может быть меньше ростом кого-либо).

Из 3 условия следует, что Браун не играет на скрипке и не играет на флейте.

Из 4 условия следует, что Смит не играет на альте и не играет на трубе.

Из 5 условия сразу понятно, что Браун не играет ни на трубе и не играет на гобое.

Получилось:

	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун	0	0			0	0
Смит	0
Вессон

Заметно, что Браун играет на кларнете и альте, следовательно, никто кроме него на них не играет.

На скрипке играет Вессон (т.к. на ней не играют Браун и Смит).

Из 2 условия Вессон не играет на флейте (он играет на скрипке). Тогда на флейте играет Смит.

Из 4 условия и из того, что Браун играет на альте, следует, что Смит не играет на трубе. Тогда на трубе играет Вессон.

Значит, Смит играет на гобое.

Окончательная таблица выглядит так:

	Скрипка	Флейта	Альт	Кларнет	Гобой	Труба
Браун	0	0	1	1	0	0
Смит	0	1	0	0	1	0
Вессон	1	0	0	0	0	1

Ответ: Браун играет на альте и кларнете; Смит играет на флейте и гобое; Вессон играет на скрипке и трубе.

4. Парадоксы

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

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

«Говорят, что в некой деревне был всего один брадобрей. Он брил всех тех и только тех мужчин, которые не брились сами. Брил ли этот брадобрей себя?»

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

Еще один пример парадокса:

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

Еще один парадокс можно найти в произведении Сервантеса «Дон Кихот»:

«…И первым делом явился к нему [Санчо Пансе] один приезжий, который в присутствии мажордома и прочей челяди заявил следующее:

- Сеньор, по владениям одного вельможи протекает многоводная река, разделяющая их на две части… Так вот, через эту реку переброшен мост, и около него стоит виселица и нечто вроде судилища, в котором обыкновенно заседают четыре судьи, наблюдая за выполнением закона, изданного владельцем реки, моста и поместья и гласящего следующее: «Каждый, переходящий по мосту с одного берега на другой, обязан под присягой заявить, куда он идёт и с какой целью; и, если он скажет правду, его пропускают дальше, если же солжёт, то его без всякого снисхождения лишают жизни, вздёрнув на стоящую рядом виселицу». С тех пор как суровые условия этого закона стали всем известны, много людей переходило через мост, и как только выяснялось, что они говорили правду, судьи позволяли им свободно следовать дальше. Но однажды случилось, что некий человек, приведённый к присяге, поклялся и заявил, подтверждая слова свои клятвой, что он пришёл сюда для того, чтобы его повесили на этой виселице. Клятва эта смутила судей, и они сказали: «Если мы позволим этому человеку свободно проследовать дальше, то выйдет, что он поклялся ложно, и в таком случае, согласно закону, должен умереть; если же мы его повесим, то ведь он поклялся, что явился сюда для того, чтобы его повесили, -- следовательно, клятва его правдива, и, согласно тому же закону, он должен быть отпущен на свободу». И вот я вас спрашиваю, ваша милость, сеньор губернатор, что делать судьям с этим человеком, потому что они и по сей день пребывают в смущении и нерешительности…»

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

Но то, что сказал этот человек, опять же приводит к парадоксу.

Не всегда удается избежать парадоксов. Самый оптимальный из предложенных путей избежать парадоксов - построение искусственного формального языка, лишенного «вольностей» языков естественных.

Заключение

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

Конечно, это далеко не все, что можно было бы затронуть в этой теме. Не затронуты более сложные аспекты такие, как дизъюнктивно-нормальная формула (ДНФ), конъюнктивно-нормальная формула (КНФ), геометрическая интерпретация формул алгебры логики.

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

1. Аксенова М., Энциклопедия для детей: математика, Т.11. В. Володин / М.Аксенова. - М.: Аванта Плюс - 2005. - 688с.

2. Мадер В.В., Школьнику об алгебре логики: Кн. для внеклас. чтения учащихся 10-11 кл. сред. шк. - М.: Просвещение - Мир знаний, 1993. - 128с.

3. Петцольд Ч., Код - М.: Русская Редакция, 2001. - 512с.

4. Шауцукова Л.З., Информатика: Учеб. пособие для 10-11 кл. общеобразоват. учреждений - 4-е изд. - М.: Просвещение, 2004. - 416с.

Размещено на Allbest.ru