Логические законы и правила преобразования логических выражений

Содержание

	Цель работы ………………………………….……………………
	Средства обучения…………………………………………………
	Теоретические сведения и рекомендации ………………………
	Задание и алгоритм выполнения работы ………………………
	Рекомендации по оформлению отчета…………………………
	Контрольные вопросы…………………………………………
	Литература ……………………………………………………………
	Приложение А…………………………………………………………
	Приложение Б ........................................................................................

ПРАКТИЧЕСКАЯ РАБОТА №3

Составление таблиц истинности. Решение логических задач.

Цель работы

4. 1 Познакомиться с основными формами, в которых осуществляется мышление, с основными логическими операциями и функциями;

4. 2 Овладеть практическими навыками решения логических задач.

Средства обучения

4. 1 методические рекомендации;

4. 2 конспекты лекций;

4. 3 дополнительная литература.

Теоретические сведения и рекомендации

Формы мышления.

Первые учения о формах и способах рассуждений возник­ли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегрече­скими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания.

Логика — это наука о формах и способах мышления.

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

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

Понятие. Понятие выделяет существенные признаки объекта, которые отличают его от других объектов. Объек­ты, объединенные понятием, образуют некоторое множест­во. Например, понятие «компьютер» объединяет множество электронных устройств, которые предназначены для обра­ботки информации и обладают монитором и клавиатурой. Даже по этому короткому описанию компьютер трудно спу­тать с другими объектами, например с механизмами, служа­щими для перемещения по дорогам и хранящимися в гара­жах, которые объединяются понятием «автомобиль».

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

Понятие имеет две стороны: содержание и объем. Содер­жание понятия составляет совокупность существенных при­знаков объекта. Чтобы раскрыть содержание понятия, сле­дует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов.

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

Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональ­ный компьютер» выражает всю совокупность (сотни миллио­нов) существующих в настоящее время в мире персональных компьютеров.

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

Высказывания могут быть выражены с помощью не толь­ко естественных языков, но и формальных. Например, вы­сказывание на естественном языке имеет вид «Два умно­жить на два равно четырем», а на формальном, математическом языке оно записывается в виде: «2 · 2 = 4».

Об объектах можно судить верно или неверно, то есть вы­сказывание может быть истинным или ложным. Истинным будет высказывание, в котором связь понятий правильно от­ражает свойства и отношения реальных вещей. Примером истинного высказывания может служить следующее: «Про­цессор является устройством обработки информации».

Ложным высказывание будет в том случае, когда оно не соответствует реальной действительности, например: «Про­цессор является устройством печати».

Высказывание не может быть выражено повелительным или вопросительным предложением, так как оценка их ис­тинности или ложности невозможна.

Конечно, иногда истинность того или иного высказывания является относительной. Истинность высказываний может зависеть от взглядов людей, от конкретных обстоятельств и так далее. Сегодня высказывание «На моем компьютере установлен самый современный процессор Реntium 4» истинно, но пройдет некоторое время, появится более мощный процес­сор, и данное высказывание станет ложным.

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

До сих пор мы рассматривали простые высказывания. На основании простых высказываний могут быть построены со­ставные высказывания. Например, высказывание «Процес­сор является устройством обработки информации, и принтер является устройством печати» является составным выска­зыванием, состоящим из двух простых, соединенных сою­зом «и».

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

Приведенное выше составное высказывание истинно, так как истинны входящие в него простые высказывания.

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

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

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

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

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

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

Для образования новых высказываний наиболее часто используют логические операции, выражаемые с помощью логических связок "И", "ИЛИ", "НЕ",.

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

НЕ Операция, выражаемая словом "не", называется отрицанием (инверсией) и обозначается чертой над высказыванием (или знаком ). Высказывание Ā истинно, когда А ложно, и ложно, когда А истинно.

Пример. "Луна - спутник Земли" (А); "Луна - не спутник Земли" (Ā).

А	Ā

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

Высказывание А·В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание "10 делится на 2 и 5 больше 3" истинно, а высказывания "10 делится на 2 и 5 не больше 3", "10 не делится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" - ложны.

А	В	А&В

ИЛИ Операция, выражаемая связкой "или" (в не исключающем смысле этого слова), называется дизъюнкцией (лат. disjuncito - разделение) или логическим сложением и обозначается знаком v (или+).

Высказывание АvВ ложно тогда и только тогда, когда оба высказывания А и В ложны.

Например, высказывание "10 не делится на 2 или 5 не больше 3" ложно, а высказывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" - истинны.

А	В	А+В

3.3 Построение таблиц истинности для сложных логических выражений.

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

При построении таблиц истинности надо руководствоваться определенной последовательностью действий:

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице, которое равно m = 2ⁿ;

3. подсчитать количество операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;

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

5. заполнить столбцы входных переменных наборами значений;

6. провести заполнение таблицы значениями (0 и 1) истинности по столбцам, выполняя логические операции.

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

Например: Построить таблицы истинности для логических выражений

a) Z = (A + B · C) + (A · C)

А	В	С	В · С	А + В · С	А	А · С	(А + В · С) + (А · С)
1

b) F = (A + B)&(A + B)

A	B	A + B	A	B	A + B	(A + B) · (A + B)

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

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

Аргу- менты

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

A

B

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

Из таблицы видно, что:
F2 -логическое умножение;
F8 - логическое сложение;
F13 -логическое отрицание для аргумента A;
F11 - логическое отрицание для аргумента B/

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

ЕСЛИ-ТО(функция F14)Операция, выражаемая связками "если...то", "из...следует", "...влечет...", называется импликацией(лат. implico -тесно связаны) или логическим следованием и обозначается знаком → (или =>).

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

Покажем на примере, как импликация связывает два элементарных высказывания : "данный четырехугольник - квадрат" (А) и "около данного четырехугольника можно описать окружность" (В). Рассмотрим составное высказывание А→В, понимаемое как "если данный четырехугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание А→В истинно:
1. А истинно и В истинно, то есть данный четырехугольник квадрат, и около него можно описать окружность;
2. А ложно и В истинно, то есть данный четырехугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырехугольника);
3. А ложно и В ложно, то есть данный четырехугольник не является квадратом, и около него нельзя описать окружность.
Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырехугольник является квадратом, но около него нельзя описать окружность.

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

А	В	А→В

ЭКВИВАЛЕНЦИЯ (функция F10) Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "...равносильно...", называетсяэквиваленцией или логическим равенством и обозначается знаком↔(может также обозначаться знаками ~ или≡).

Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.

А	В	А≡В

3.5 Построение таблиц истинности логических функций и выражений.

Вспомним алгоритм построения таблиц истинности:

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице, которое равно m = 2ⁿ;

3. подсчитать количество операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;

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

5. заполнить столбцы входных переменных наборами значений;

6. провести заполнение таблицы значениями (0 и 1) истинности по столбцам, выполняя логические операции.

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

ПРИМЕР 1

Построим таблицу истинности для логического выражения

Y=(A→(B→C))~(A&B&C)

A	B	C	B→C	A→(B→C)	(A→(B→C))	C	A&B	A&B&C	Y

2. Сколько различных решений имеет уравнение

K	L	M	N

Ответ: 4.

Логические законы и правила преобразования логических выражений

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

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

2.Закон непротиворечия.Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным.
Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

А & А = О

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

А V А = 1

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

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

A V B = A&B A&B = A V B

Важное значение для выполнения преобразований логи­ческихвыражений имеют законы алгебраических преобра­зований. Многие из них имеют аналоги в обычной алгебре.

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

Логическое умножение A&B= B&A

Логичекое сложение A V B= B V A

7 Закон ассоциативности.Если в логическом выражении

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

Логическое умножение Логическое сложение

(А& В) &С= А &(В&С) (А V В) V С =А V (ВV С)

8 Закон дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как об­щие множители, так и общие слагаемые:

Дистрибутивность умножения Дистрибутивность сложения
относительно сложения относительно умножения ab+ac=a(b+c) в алгебре

(A&B) V (A&C)= А& (B V C) (А v В) & (А v С) = А у (В & С)

ПРИМЕР 2

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

(А & В) v (А & В).

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

(А & В) v (A & В) = А & (ВVВ).

2. По закону исключенного третьего В v В =1, следователь­но:

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

3.7 Решение логических задач

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

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

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

· табличный;

· с помощью графов.

3.7.1 Рассмотрим решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

ЗАДАЧА 1

В соревнованиях по гимнастике на первенство школы участвуют Алла, Валя, Таня и Даша. Болельщики высказали предположения о возможных победителях:
1: “Первой будет Таня, Валя будет второй”.
2: “Второй будет Таня, Даша - третьей”.
3: “Алла будет второй, Даша - четвертой”.
По окончании соревнований оказалось, что в каждом предположении только одно из высказываний истинно, другое же ложно. Какое место на соревнованиях заняла каждая из девочек, если все они оказались на разных местах?

Решение. Введем буквенные обозначения всех высказываний, задающих условие задачи:
T₁ - “Таня будет первой”;
W₂ - “Валя будет второй”;
T_{2 -} “Таня будет второй”;
D_{3 -} “ Даша будет третьей”;
A_{2 -} “ Алла будет второй”;
D₄ - “Даша будет четвертой”.
Высказывание каждого болельщика о двух спортсменах можно задать формулами:

Помним, что в условии сказано: в каждом предположении только одно из высказываний истинно, другое ложно. Следует учесть и то, что ни одно место не было разделено участниками.
Это условие можно задать формулами:
То обстоятельство, что ни один участник не может занять два разных места, задано формулами (7) и (8).

Система уравнений решается умножением одного уравнения на другое и нахождением истинного выражения.
Умножая уравнение (1) на (2), получим:

Умножаем полученное уравнение (9) на (3), получаем:

Итак, мы получим ответ:

Ответ:Таня - первая; Валя - четвертая; Даша - третья; Алла - вторая.