Презентация для обобщающего урока по теме "Логические основы построения компьютера"

ЛОГИКА

Суховершина Светлана Тимофеевна, учитель информатики МОУ - технического лицея № 176 Карасукского района Новосибирской области

Основной объект изучения логики

• Основной объект изучения логики - элементарные высказывания. Из них с помощью логических связок (элементарных операций) строятся сложные высказывания.
• При алгебраическом подходе эти высказывания рассматриваются как формулы, которые можно вычислять и преобразовывать. Логическими переменными обозначают элементарные высказывания. Формулы определяют логические функции.
• Логические функции, переменные, элементарные операции образуют алгебру Буля (булеву алгебру). Для булевой алгебры справедливы определенные соотношения, тождества, правила и законы.
• Булева функция - функция, как и ее аргументы принимающая только два значения: 0 и 1. Совокупность значений аргументов называется набором. Всего может быть 2 N наборов аргументов.
• Функция может быть задана таблично (таблица истинности), числовым способом, аналитически (в виде СДНФ или СКНФ), графически (картой Карно).
• Цель минимизации - упрощение СДНФ (СКНФ), чтобы в минимальной форме было наименьшее возможное число букв и наименьшее возможное число знаков операций.
• Чтобы решить логическую задачу, необходимо найти истинное высказывание, отвечающее на поставленный в задаче вопрос.

В и (¬А) \/ В равносильны, а А \/ В и А /\ В – нет (значения выражений разные, например, при А = 1, В = 0). Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность). инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность). инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность)." width="640"

• Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А – В и (¬А) \/ В равносильны, а А \/ В и А /\ В – нет (значения выражений разные, например, при А = 1, В = 0).
• Приоритеты логических операций:

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

Таким образом, ¬А /\ В \/ С /\ D совпадает с ((¬А) /\ В) \/ (С /\ D).

Возможна запись А /\ В /\ С вместо (А /\ В) /\ С.

То же относится и к дизъюнкции:

возможна запись А \/ В \/ С вместо (А \/ В) \/ С.

Таблицы истинности

Дизъюнкция, логическое «или»

Инверсия, логическое «не»

А

0

В

А или В

0

0

0

1

1

1

0

1

1

1

1

а

0

Не а

1

1

0

Импликация, «если …, то …)

Конъюнкция, логическое «и»

А

0

В

0

Если А, то В

0

1

1

1

1

1

0

0

1

1

А

0

В

А и В

0

0

0

1

1

1

0

0

0

1

1

А

0

В

А равносильно В

0

0

1

1

1

1

0

0

0

1

1

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

(например, А – В); e) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания)." width="640"

Обозначения для логических связок (операций):

a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

b) конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В) либо & (например, А & В);

c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В) либо | (например, А | В);

d) следование (импликация) обозначается –

(например, А – В);

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

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

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

• Сочетательный:
• Распределительный:
• Закон непротиворечия:

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

• Закон исключенного третьего:
• Закон двойного отрицания:
• Законы де Моргана:
• Законы идемпотентности:

Правила замены операций:

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

• Вычислить количество строк и столбцов таблицы истинности.

Пусть сложное высказывание состоит из n простых. Тогда кол-во строк в таблице равно 2 n + 2 троки заголовка.

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

• Пусть сложное высказывание состоит из n простых. Тогда кол-во строк в таблице равно 2 n + 2 троки заголовка. Кол-во столбцов равно сумме количества переменных (n) и количества логических операций, входящих в высказывание
• Пусть сложное высказывание состоит из n простых. Тогда кол-во строк в таблице равно 2 n + 2 троки заголовка. Кол-во столбцов равно сумме количества переменных (n) и количества логических операций, входящих в высказывание

• Начертить таблицу и заполнить заголовок

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

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

• Заполнить столбцы.

Четвертая буква имени согласная) Елена 3. Антон Вадим 4. Федор Решение: по правилам замены операций , по закону де Моргана Значит  (  А  В)=А  В (Первая буква имени гласная и четвертая не согласная = первая буква имени гласная и четвертая гласная) Ответ: 3 - Антон" width="640"

Решение задач

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

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

• Елена 3. Антон
• Вадим 4. Федор

Решение: по правилам замены операций , по закону де Моргана

Значит  (  А  В)=А  В (Первая буква имени гласная и четвертая не согласная = первая буква имени гласная и четвертая гласная)

Ответ: 3 - Антон

Решение задач

Пример 2 . Какое логическое выражение равносильно выражению:

 (А  В)?

1. А  В 2. А  В 3. (  А)  (  В ) 4. (  А)  В

Решение : Воспользуемся тождествами:

1.  (A  В)=(  A)  (  В) 2.  В=В.

Получим высказывание:  (А  В)= (  А)  В

Решение задач

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

X

Y

0

0

Z

0

F

0

0

0

1

1

1

0

0

1

Решение: чтобы не строить таблицу истинности для каждого выражения, можно перепроверить предложенные ответы

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

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

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

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

1.  Х   Y  Z

2.  Х   Y  Z

3. Х  Y   Z

4. Х  Y  Z

Ответ: 3.

(  L  M  N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M, N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1. Решение: А=B=  A  В;  (A  В)=(  A)  (  В);  (  A)=A. (  К  М)=(  L  M  N)=  (  К  М)  (  L  M  N)= (К  М)  (  L  M  N). (К  М)  (  L  M  N)=0 – для выполнения этого равенства необходимо, чтобы  L  M  N=0 (1) и К  М=0 (2). (1) выполняется лишь при L=1, M=0, N=0. Рассмотрим (2). Так как М=0 (т.е.  М=1), то К=0. Таким образом получим ответ: К=0, L=1, M=0, N=0. ОТВЕТ: 0100." width="640"

Решение задач

Пример 4. Укажите значения переменных K, L, M, N, при которых значение (  К  М)=(  L  M  N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M, N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение: А=B=  A  В;  (A  В)=(  A)  (  В);  (  A)=A.

(  К  М)=(  L  M  N)=  (  К  М)  (  L  M  N)= (К  М)  (  L  M  N).

(К  М)  (  L  M  N)=0 – для выполнения этого равенства необходимо, чтобы  L  M  N=0 (1) и К  М=0 (2).

(1) выполняется лишь при L=1, M=0, N=0.

Рассмотрим (2). Так как М=0 (т.е.  М=1), то К=0.

Таким образом получим ответ: К=0, L=1, M=0, N=0.

ОТВЕТ: 0100.

Решение задач

Пример 5. X, Y, Z – целые числа, для которых истинно высказывание: ((Z

Решение: Преобразуем данное высказывание:

((Z

Подставим значения X и Y:

((Z

Заметим, что (Z  19)  (Z  9)= (Z  19) .

((Z

Воспользуемся распределительным свойством:

((Z

Высказывание (Z

((Z

Существует единственное число меньшее 20 и, при этом большее или равное 19.

Это число 19.

ОТВЕТ: 19.

Решение задач.

Пример 6 . Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на синем «Рено», Джон сказал, что нарушитель уехал на черной «Тойоте», а Сэм показал, что машина точно была не синяя и, по всей видимости, это был «Форд». Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля, а в другом ошибся. Какая и какого цвета была машина у нарушителя? Ответ запишите в виде двух слов, разделенных пробелом: МАРКА ЦВЕТ. (Пример: ЖИГУЛИ БЕЛЫЙ).

Решение: Обозначим высказывания:

А=«машина синего цвета»

В=«машина была «Рено»

С=«машина черного цвета»

D=«машина была «Тойота»

Е=«машина была «Форд»

Согласно условию:

Из показаний Боба следует: А  В истинно;

Из показаний Джона следует: С  D истинно;

Из показаний Сэма следует:  A  E истинно.

Решение задач

Пример 6 .(продолжение)

Следовательно, истинна и конъюнкция (A  В)  (C  D)  (  A  E)=1

Раскрывая скобки, получим:

(A  В)  (C  D)  (  A  E)=(A  C  A  D  В  C  В  D)  (  A  E)=(A  C  A)  (A  D  A)  (В  C  A)  (В  D  A)  (A  C  E)  (A  D  E)  (В  C  E)  (В  D  E)=1

Из полученных восьми слагаемых семь (согласно условию задачи) являются ложными. Остается единственное слагаемое: В  C  A=1.

А=«машина синего цвета»

В=«машина была «Рено»

С=«машина черного цвета»

Значит, нарушитель скрылся на автомобиле «Рено» черного цвета.

ОТВЕТ: РЕНО ЧЕРНЫЙ.

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

1. ЕГЭ. Информатика: Типовые тестовые задания / И.Ю. Гусева. – СПб.: Тритон, 2009

2. Единый государственный экзамен 2008. Информатика. Учебно-тренировочные материалы для подготовки учащихся / ФИПИ – М.: Интеллект-Центр, 2007

3. Информатика и ИКТ. Подготовка к ЕГЭ/Под ред. Проф. Н.В.Макаровой. – СПб.: Питер, 2008.

4. Зорина Е.М. ЕГЭ 2010: Информатика: сборник заданий/Е.М.Зорина, М.В.Зорин. – М.: Эксмо, 2009

Электронные ресурсы:

1. www.edu.ru,

2. www.ege.edu.ru

3. www.ege.spb.ru

4.http:// letopisi.ru/index.php/Вики_учебник_для_подготовки_к_ЕГЭ/Раздел_Информатика

5. http://www.fipi.ru

6. http://www.alleng.ru/edu/comp2.htm ( на этом сайте можно скачать книги по подготовке к ЕГЭ)