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

176 Карасукского района Новосибирской области

Из них с помощью логических связок (элементарных операций) строятся сложные

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

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

–> В и (¬А) \/ В равносильны, а А \/ В и А /\ В – нет (значения выражений разные, например, при А = 1, В = 0).


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

Таким образом, ¬А /\ В \/ С /\ D совпадает с ((¬А) /\ В) \/ (С /\ D).
Возможна запись А /\ В /\ С вместо (А /\ В) /\ С.
То же относится и к дизъюнкции:
возможна запись А \/ В \/ С вместо (А \/ В) \/ С.

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

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

b) конъюнкция (логическое умножение, логическое И) обозначается

/\ (например, А /\ В) либо & (например, А & В);

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

d) следование (импликация) обозначается –>
(например, А –> В);

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

сложное высказывание состоит из n простых. Тогда кол-во строк в

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

имени гласная => Четвертая буква имени согласная)
Елена

3. Антон
Вадим 4. Федор
Решение: по правилам замены операций , по закону де Моргана

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

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

2. А∨В 3. (¬А)

∨(¬В) 4. (¬А) ∧В
Решение: Воспользуемся тождествами:
1. ¬(A∨В)=(¬A)∧(¬В) 2. ¬¬В=В.

Получим высказывание: ¬(А∨¬В)=(¬А) ∧В

логических выражений от трех аргументов: X, Y, Z. Дан фрагмент

таблицы истинности выражения F. Какое выражение соответствует F?

1. ¬Х∧ ¬Y ∧Z
2. ¬Х∨ ¬Y ∨ Z
3. Х∨Y ∨ ¬ Z
4. Х∨Y ∨ Z

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

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, что не соответствует второй строке таблицы

Ответ: 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.

которых истинно высказывание: ((Z

Y=10?
Решение: Преобразуем данное высказывание:
((ZПодставим значения X и Y:

((Z<20)∨(Z<10)∧((Z+1)≥20) ∧((Z+1) ≥10)=((Z<20)∨(Z<10)∧(Z≥19) ∧(Z ≥ 9).
Заметим, что (Z≥19) ∧(Z ≥ 9)= (Z≥19) .
((Z<20)∨(Z<10)∧(Z≥19) ∧(Z ≥ 9)= (Z<20)∨(Z<10)∧(Z≥19)
Воспользуемся распределительным свойством:
((Z<20)∨(Z<10)∧(Z≥19)= ((Z<20)∧(Z≥19) ∨((Z<10)∧(Z≥19) ).
Высказывание (Z<10)∧(Z≥19) тождественно ложное, поэтому
((Z<20)∧(Z≥19) ∨((Z<10)∧(Z≥19) ). = ((Z<20)∧(Z≥19).
Существует единственное число меньшее 20 и, при этом большее или равное 19.
Это число 19.
ОТВЕТ: 19.

скрывшемся нарушителе. Боб утверждает, что тот был на синем «Рено»,

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

Согласно условию:
Из показаний Боба следует: А∨В истинно;
Из показаний Джона следует: С∨D истинно;
Из показаний Сэма следует: ¬A∨ E истинно.

полученных восьми слагаемых семь (согласно условию задачи) являются ложными. Остается

единственное слагаемое: В∧C∧¬A=1.
А=«машина синего цвета»
В=«машина была «Рено»
С=«машина черного цвета»
Значит, нарушитель скрылся на автомобиле «Рено» черного цвета.
ОТВЕТ: РЕНО ЧЕРНЫЙ.

Гусева. – СПб.: Тритон, 2009
2. Единый государственный экзамен 2008.

Информатика. Учебно-тренировочные материалы для подготовки учащихся / ФИПИ – М.: Интеллект-Центр, 2007
3. Информатика и ИКТ. Подготовка к ЕГЭ/Под ред. Проф. Н.В.Макаровой. – СПб.: Питер, 2008.
4. Зорина Е.М. ЕГЭ 2010: Информатика: сборник заданий/Е.М.Зорина, М.В.Зорин. – М.: Эксмо, 2009

этом сайте можно скачать книги по подготовке к ЕГЭ)