Законы алгебры логики Задания для самостоятельного решения




Скачать 412.93 Kb.
НазваниеЗаконы алгебры логики Задания для самостоятельного решения
страница1/2
Дата30.08.2012
Размер412.93 Kb.
ТипЗакон
  1   2

Практикум по решению задач в курсе информатики. Лебедева Э.В,

Центр информатизации и оценки качества образования


Модуль 3. Математические и логические основы информатики


1. Основные понятия математической логики

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

3. Задания для самостоятельного решения


1. Основные понятия математической логики

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

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

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

Рассмотрим примеры логических высказываний (см. Таблицу 1):

Таблица 1. Примеры логических выражений

Предложение

Характеристика с точки зрения алгебры логики

Иваново – Родина Первого Совета

Истинное логическое высказывание

За зимой наступит весна

Истинное логическое высказывание

В городе Иваново проживают только граждане России

Ложное логическое высказывание

После дождя всегда тепло

Ложное логическое высказывание

После вторника будет выходной

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

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

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

А и В.

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

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

Таблица 2. Логические связки



Логическая связка

Название

Обозна-чение

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

Математическая запись

1

и

конъюнкция

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

, 

*, And

A и В

A  B, A  B

A * B, A And B

2

или

дизъюнкция

логическое сложение



+, Or

A или В

A  B

A + B, A Or B

3

не

инверсия,

логическое отрицание

¬, ,

Not

не А

¬А, ,

Not A

4

Если…то

импликация,

логическое следование

→, 

Если A, то В

A → B

A  B

5

тогда и только тогда

эквивалентность, равносильность,

логическое тождество

, 

, 

А тогда и только тогда, когда В

АВ, АВ

АВ, АВ

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

A → B = ¬А  B

(1)

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

A  B = (¬А  B)  (¬B  А)

(2)

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

Таблица 3. Таблица истинности

A

B

A  B

A  B

¬A

0

0

0

0

1

0

1

1

0

1

1

0

1

0

0

1

1

1

1

0

Таблица 4. Приоритет выполнения логических операций

Приоритет операции

Логическая операция

Первый (высший)

Логическое отрицание

Второй

Конъюнкция (логическое умножение)

Третий

Дизъюнкция (логическое сложение)

Четвертый

Импликация (следование)

Пятый (низший)

Эквивалентность (равносильность)



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

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

Таблица 5. Основные законы алгебры логики

Закон

Для ИЛИ

Для И




Переместительный

xy = yx

xy = yx

(3)

Сочетательный

x(yz) = (xy)z

x(yz) = (xy)z

(4)

Распределительный

x(yz) = xy xz

x yz = (xy)  (xz)

(5)

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

¬( xy)= ¬x(¬y)

¬(xy)= ¬x(¬y)

(6)

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

xx=x

xx=x

(7)

Поглощения

xxy=x

x(xy)=x

(8)

Склеивания

xy(¬x)y=y

(xy) (¬xy)=y

(9)

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

x(¬x)=1

x(¬x)=0

(10)

Операция с константами

x1=x; x0=х

x1=x; x0=0

(11)

Операция двойного отрицания

¬(¬x)=x

(12)


Задание 1. (Задание А11 демоверсии 2004 г.)

Для какого имени истинно высказывание:

¬(Первая буква имени гласная → Четвертая буква имени согласная)

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР


Решение.

Введем обозначения для высказываний:

А = «Первая буква имени гласная»

(13)

В = «Четвертая буква имени согласная»

(14)

тогда наше высказывание примет вид: ¬(A → B). Чтобы преобразовать высказывание, воспользуемся тождествами (1), (6), (12):

(1)

(6)

(12)

¬(A → B) = ¬((¬A)  B) = ¬(¬A)  (¬B) = A  (¬B)

Используя обозначения (13), (14), получим, что исходное высказывание равносильно следующему:

Первая буква гласная  ¬(Четвертая буква имени согласная), 

Первая буква гласная  Четвертая буква имени гласная.

Этому условию удовлетворяет только имя АНТОН (вариант ответа №3).

Ответ: 3

Задание 2. (Задание А12 демоверсии 2004 г.)

Какое логическое выражение равносильно выражению ¬(A  ¬B)

1) AB

2) AB

3) ¬A¬B

4) ¬AB


Решение.

Чтобы преобразовать высказывание, воспользуемся законами (6), (12):

(6) (12)

¬(A  ¬B) = ¬A  ¬(¬B) = ¬A  B, что соответствует ответу №4.

Ответ: 4

Задание 3. (Задание А13 демоверсии 2004г., А11 демоверсий 2005, 2006г.)

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

1

Какое выражение соответствует F?

1) ¬X¬YZ

2) ¬X¬YZ

3) XY¬Z

4) XYZ


Решение.

Способ 1. Наличие двух единиц в столбце F позволяет предположить использование дизъюнкции в логическом выражении. F принимает значение, равное 0, при X=0, Y=0, Z=1, что соответствует логической сумме XY¬Z. При проверке этой формулы при значениях первой и третьей строки, получаем верные значения F.

Способ 2. Проверим предложенные ответы:

  1. F=¬X¬YZ=0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы.

  2. F=¬X¬YZ=1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

  3. Выражение XY¬Z соответствует F при всех предложенных комбинациях X,Y,Z.

  4. F=XYZ=1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Таким образом, верный вариант ответа №3.

Ответ: 3

Задание 4. (Задание А9 демоверсий 2005 г., 2006 г.)

Для какого числа X истинно высказывание




X>1  ((X<5)→(X<3))

(15)

















1) 1

2) 2

3) 3

4) 4


  1   2

Похожие:

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

Законы алгебры логики Задания для самостоятельного решения iconФормы мышления. Алгебра логики
Создать организационные и содержательные условия для формирования представлений учащихся о понятиях алгебры логики
Законы алгебры логики Задания для самостоятельного решения iconИсследование новых моделей задач математической физики и создание алгоритмов их решения. В рамках этого проекта: подпроект «Законы сохранения, инварианты, точные и приближенные решения для уравнений гидродинамического типа и интегральных уравнений»
Математические проблемы алгебры, топологии, теории приближения функций и приложения
Законы алгебры логики Задания для самостоятельного решения iconПрограмма по курсу: основы теории
Элементы алгебр логики. Полные наборы функций алгебры логики. Комбинаторные схемы
Законы алгебры логики Задания для самостоятельного решения iconПрограмма дисциплины по кафедре Прикладная математика
Охватывает круг вопросов, связанных с изучением формальных теорий, элементов теории множеств, логики высказываний и логики предикатов,...
Законы алгебры логики Задания для самостоятельного решения iconЫ и темы рабочей программы для самостоятельного изучения Перечень домашнего задания и других вопросов для самостоятельного изучения
«Основы безопасности жизнедеятельности» В. А. Алексеенко, начальное профессиональное образования для училищ и лицеев. 2001г
Законы алгебры логики Задания для самостоятельного решения iconЗаконы сохранения
Решения и критерии оценивания знаний учащихся к части 3: (задания с развёрнутым ответом)
Законы алгебры логики Задания для самостоятельного решения iconТема основы логики (первый этап отношений логики и языка) (6 часов)
История логики. Логика и язык. Миф о полной ограниченности и неприменимости логики в сфере языкознания. Миф о всесилии логики и семиотики...
Законы алгебры логики Задания для самостоятельного решения iconПрограмма элективного курса для предпрофильной подготовки учащихся 9 классов по математике
Он посвящен одной из самых сложных и актуальных тем курса алгебры – заданиям с параметрами, связанными с квадратным трехчленом. Такие...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница