Алгоритмы решения логических задач




РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ.

Введение

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

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

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

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

Целью данной работы было рассмотрение следующих вопросов:

 

1. История логики, ее родословная.

2. Что является объектами изучения алгебры Буля и какие логические операции можно производить над ними.

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

4. Как помогает Булева алгебра при решении практических задач? Разнообразие логических задач велико. Способов решения их достаточно много, но основными являются три, которые и рассмотрены в реферате.

5. Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

История логики


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

Родословная логики связана с философскими размышлениями о правилах спора и процедурах убеждения, поэтому сначала логика была скорее вспомогательной частью риторики и юриспруденции. Так было до Аристотеля. Развитие науки логики на протяжении ряда столетий протекало по двум направлениям. Одно из них начиналось с древнегреческой логики (в особенности с логики Аристотеля), на основе которой развивалась логика в Древнем Риме, затем Византии, Турции, Армении, арабоязычных странах Ближнего Востока, в Западной Европе и России. Другое направление имело своим истоком индийскую логику, на основе которой развивалась логика в Китае, Тибете, Монголии, Корее, Японии, Индонезии, на Цейлоне.

Основателем логики, как науки, считают Сократа (469-399 гг до н.э.). На первый план он выдвинул проблему метода, посредством которого можно получить истинное знание. Сократ считал, что любой предмет может быть познан лишь в том случае, если его можно свести к общему понятию и судить о нем на основе этого понятия. Познание "по Сократу" происходило следующим образом. На площади собиралось большое количество людей. Сократ просил их дать определение какого-либо понятия (например, " справедливость"). Выслушивая определения одно за другим, он показывал несовершенство каждого, каждый раз требуя более полного и точного. Таким образом, приближаясь к верному определению понятия, люди приближались к "познанию " этого понятия. Знание для Сократа – это понятие о предмете, и достигается оно посредством определения понятия.

Аристотель (384-322 гг до н.э.) - отец европейской логической традиции, разработавший способы построения умозаключений (силлогизмов)и их оценки. Аристотель обучался наукам в академии Платона. После смерти великого учителя он переехал в Афины. Там Аристотель взялся за создание собственного учебного заведения, которое располагалось рядом с городским садом и от этого получило название "ликей" (сад). Аристотель преподавал, прогуливаясь с учениками по саду. Такой метод назывался "схолэ".


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

Т ак было до того момента, когда в XIX веке англичанин ^ Джордж Буль(Boole) (1815-1864) пошел на спор, что создаст науку, совершенно оторванную от действительности и не имеющую ни малейшего практического применения. Он превратил мат. логику в АЛГЕБРУ СУЖДЕНИЙ. Булева алгебра - наука о действиях над суждениями (высказываниями). Буль произвел революцию в науке, о которой сам не подозревал. То, во что он превратил логику, было в дальнейшем положено в основу построения электронно-вычислительных устройств. История показала, что спор Булем был проигран. Из всей логики именно Булева алгебра получила самое большое практическое применение в технике.


Дальнейшее усовершенствование алгебры логики было осуществлено английским логиком У.С. Джевонсом (1835-1882), немецким логиком Э. Шредером (1841-1902), русским логиком П.С. Порецким (1846-1907) и другими.

В последующих трудах по алгебре логики немецкого логика Г. Фреге (1848-1925), разработавшего теорию исчисления высказываний, немецкого логика и математика Д. Гильберта (1862-1943), английского философа и логика Б. Рассела (1872-1970), придавшего (вместе с Уайтхедом) математической логике современный вид, русского логика и математика И.И. Жегалкина (1869-1947), заслугой которого явилась дальнейшая разработка исчисления классов и значительное упрощение теории операций логического сложения, предмет алгебры логики вышел далеко за рамки изучения обычных операций с понятиями.

Применение булевой алгебры в технике, как об этом пишет Г.И. Поваров, было впервые осуществлено в России известным физиком П. Эренфестом (1910 г.) и известным специалистом по гидротехническим сооружениям М.М. Герсевановым, который использовал булеву алгебру для исследования связей между различными упрощающими гипотезами при расчете гидротехнических сооружений. Приблизительно до 1930-х годов логическая теория представляла, в основном, академический интерес и не была связана с потребностями прикладных наук. С этого момента начинают развиваться теории релейно-контактных схем, а затем общие теории анализа и синтеза абстрактных автоматов.

Строгие доказательства применимости булевой алгебры в теории контактных и релейно-контактных схем были даны в 1938 году русским физиком В.И. Шестаковым и американским математиком К.Э. Шенноном. Область логических методов анализа и синтеза схем бурно развивалась в 50-е и начале 60-х годов и к середине 60-х годов стала сложившейся научной дисциплиной с развитым аппаратом и определенной областью исследований. К.Э.Шеннон


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


2. Алгебра высказываний. Основные логические операции


Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются понятие, высказывание, умозаключение.

Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.

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

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


Объектами алгебры высказываний являются повествовательные предложения, относительно каждого из которых имеет смысл говорить истинно оно или ложно. Такие предложения называются простыми высказываниями. Например: «Липецк – город металлургов» - истинное высказывание, «Минск – столица Украины» - ложное высказывание.

В алгебре высказываний высказывания обозначаются именами логических переменных: А=1 (если высказывание истинно), А=0 (если высказывание ложно).

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

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

1. Операция, выражаемая связкой “и”, называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается знаком & (может также обозначаться знаками ^ или •). Высказывание А & В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Пример: Высказывание “10 делится на 2 и 5 больше 3” истинно, а высказывания “10 делится на 2 и 5 не больше 3”, “10 не делится на 2 и 5 больше 3”, “10 не делится на 2 и 5 не больше 3” ложны.

2. Операция, выражаемая связкой “или” (в неразделительном, неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Пример: Высказывание “10 не делится на 2 или 5 не больше 3” ложно, а высказывания “10 делится на 2 или 5 больше 3”, “10 делится на 2 или 5 не больше 3”, “10 не делится на 2 или 5 больше 3” истинны.

3. Операция, выражаемая словом “не”, называется отрицанием и обозначается чертой над высказыванием. Высказывание A истинно, когда A ложно, и ложно, когда истинно.

Пример: «Луна – спутник Земли» (А истинно), «Луна – не спутник Земли» (А ложно).

4. Операция, выражаемая связками “если..., то”, “из... следует”, “... влечет...”, называется импликацией (лат. implico — тесно связаны) и обозначается знаком =>. Высказывание А => В ложно тогда и только тогда, когда А истинно, а В — ложно. Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: “данный четырёхугольник — квадрат” (А) и “около данного четырёхугольника можно описать окружность” (В). Рассмотрим составное высказывание А В, понимаемое как “если данный четырёхугольник квадрат, то около него можно описать окружность”. Есть три варианта, когда высказывание А =>В истинно:

1. А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

2. А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

3. A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.


5. Операция, выражаемая связками “тогда и только тогда”, "необходимо и достаточно”, “... равносильно...”, называется эквивалентностью или двойной импликацией и обозначается знаком <=> или ~. Высказывание А <=> В истинно тогда и только тогда, когда значения А и В совпадают.

Пример: высказывания “24 делится на 6 тогда и только тогда, когда 24 делится на 3”, “23 делится на 6 тогда и только тогда, когда 23 делится на 3” истинны, а высказывания “24 делится на 6 тогда и только тогда, когда 24 делится на 5”, “21 делится на 6 тогда и только тогда, когда 21 делится на 3” ложны.

Итак, мы рассмотрели пять логических операций. Однако, импликацию можно выразить через дизъюнкцию и отрицание. Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию. Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (“не”), затем конъюнкция (“и”), после конъюнкции — дизъюнкция (“или”) и в последнюю очередь – импликация, эквивалентность.

 

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

A B A&B AVB A=>B A<=>B
0 0 0 0 1 1 1
0 1 0 1 1 0  
1 0 0 1 0 0 0
1 1 1 1 1 1  


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

Логическая функция - это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1. С помощью логических переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить логической функцией. Обычно значения логических функций записываются в виде таблиц (т.н. таблицы истинности). Число строк в такой таблице - это число возможных наборов значений аргументов. Оно равно 2n, где n - число переменных. Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.

Как построить таблицу истинности логической функции, содержащей более одной логической связки. Удобной формой записи при нахождении значений функции является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул. Здесь необходимо помнить, что существует приоритет логических операций: действия в скобках, отрицание (не), конъюнкция (и &), дизъюнкция (или V), импликация =>, эквивалентность<=>.

Пример. Построить таблицу истинности для логической функции

y = А v v &C

Переменные Промежуточные логические формулы Функция
A B C А v А v &C А v v &C
0 0 0 1 1 0 1 0 0
0 0 1 1 1 0 1 1 1
0 1 0 0 0 1 1 0 1
0 1 1 0 0 1 1 1 1
1 0 0 1 1 0 0 0 0
1 0 1 1 1 0 0 0 0
1 1 0 0 1 0 0 0 0
1 1 1 0 1 0 0 0 0

Законы алгебры логики

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

Закон тождества. Всякое высказывание тождественно самому себе: А = А.

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. А & = 0.

Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. А v = 1.

Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание. = А.

Законы де Моргана. = &

= v .

Следующие три закона имеют аналоги в обычной алгебре.

Закон коммутативности. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:

А & В = В & А А v В = В v А.

^ Закон ассоциативности. Если в логическом выражении используются только операции логического сложения или логического умножения, то можно пренебрегать скобками или произвольно их расставлять:

(А & В) & С = А & (В & С) (А v В) v С = А v (В v С).

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

(А & В) v (А & С) = А & (В v С) (А v В) & (А v С) = А v (В &С).

Закон поглощения. A v (B & A) == A A & (B v A) == A

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

Рассмотрим пример: 1. Доказать справедливость закона поглощения.

A&(AvB) = A&AvA&B = AvA&B =A&1vA&B = A&(1vB) = A&1 = A.

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

2. Упростить логическое выражение:

(А v ) &B = 1 &B = В; при упрощении этого выражения использовался закон исключенного третьего.

A & (A v B) & (В v ) = А & В v (А & ) = А & (В v ) = А & 1 = А; здесь использован законы дистрибутивности сложения относительно умножения и умножения относительно сложения, а также закон исключенного третьего.

A & (A v B) & (В & ) = A & (A v B) & 0 = 0; для преобразования данного логического выражения использован закон непротиворечия.

Алгоритмы решения логических задач

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


  • средствами алгебры логики;

  • табличный;

  • с помощью рассуждений.


Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-11 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: