- •Алгоритмы,
- •НАЗНАЧЕНИЯ АЛГОРИТМОВ
- •НЕРАЗМЫШЛЯЮЩИЙ
- •АЛГОРИТМЫ
- •Виды алгоритмов
- •СВОЙСТВА АЛГОРИТМОВ
- •СВОЙСТВА АЛГОРИТМА
- •СВОЙСТВА
- •СВОЙСТВА
- •КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ
- •КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ
- •Начал
- •РАЗРАБОТКА
- •ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ СТРУКТУРЫ АЛГОРИТМА
- •БЛОК-СХЕМА
- •БАЗОВЫЕ КОНСТРУКЦИИ АЛГОРИТМА
- •АЛГОРИТМИЧЕСКИЕ
- •АЛГОРИТМИЧЕСКИЕ
- •АЛГОРИТМИЧЕСКИЕ
- •АЛГОРИТМИЧЕСКИЕ
- •ПРИМЕР
- •Истина
- •БАЗОВЫЕ АЛГОРИТМЫ
- •БАЗОВЫЕ АЛГОРИТМЫ
- •БАЗОВЫЕ АЛГОРИТМЫ
- •Пример.
- •БАЗОВЫЕ АЛГОРИТМЫ
- •Пример. Вычислить сумму N первых натуральных чисел. Использовать цикл с предусловием.
- •Пример.
- •ТРЕНИН
- •ТРЕНИН
- •Пример.
- •ТРЕНИНГ
- •ПРИМЕ Р 7
- •ТРЕНИНГ
- •ВСПОМОГАТЕЛЬНЫЕ
- •ВСПОМОГАТЕЛЬНЫЕ
- •ВСПОМОГАТЕЛЬНЫЕ
- •1. Могилев А.В. Информатика / А. В. Могилев, Н. И. Пак, Е. К.
- •ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
- •ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
- •Формы
- •Формы
- •Формы
- •Формы
- •Алгебра высказываний служит для определения истинности или ложности составных высказываний, не вникая в
- •СОСТАВНОЕ ВЫСКАЗЫВАНИЕ содержит высказывания, объединенные логическими операциями.
- •Логическое умножение (конъюнкция) -
- •Пример 1.
- •Логическое сложение (дизъюнкция)-
- •Логическое отрицание (инверсия) –
- •Импликация двух высказываний A и B - такое высказывание, которое ложно тогда и
- •Эквиваленция двух высказываний A и B - такое высказывание, которое истинно тогда и
- •Логической переменной называется переменная, значением которой может быть любое высказывание, например: x, у,
- •Формулы А и B, зависящие от одного и того же набора переменных x1,
- •ПРИОРИТЕТ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
- •ЛОГИЧЕСКИЕ ФУНКЦИИ
- •ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ
- •БУЛЕВЫ ФУНКЦИИ ДВУХ АРГУМЕНТОВ
- •Инверсия
- •Основные законы и тождества булевой
- •Любой из основных законов и тождеств булевой алгебры может быть доказан с помощью
- •Законы алгебры логики можно доказать
- •Законы алгебры логики можно доказать путем тождественных преобразований.
- •Формула А называется тавтологией (или тождественно истинной),
- •Формула А называется тождественно ложной,
- •Пример 11. Определить x, если:
- •Пример 12.
- •Пример 13.
- •Любую формулу можно преобразовать к равносильной ей, в которой используются только операции НЕ,
- •Пример 15.
- •Пример 16.
- •Решение логических задач
- •Пример 17.
- •На вопрос «Кто из трех студентов изучал
- •Пример 18.
- •Таблица истинности для F1
- •Таблицы истинности. Обучающая программа «Logic»
- •БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ ЭВМ
- •Логические элементы компьютера
- •КОНЪЮНКТОР
- •ДИЗЪЮНКТОР
- •ИНВЕРТОР
- •ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ
- •КАНОНИЧЕСКИЕ ФОРМЫ БУЛЕВЫХ
- •КАНОНИЧЕСКИЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ
- •СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА (СДНФ) логической функции
- •ПОЛУЧЕНИЕ СДНФ ФУНКЦИИ С ПОМОЩЬЮ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ
- •ПЕРЕХОД ОТ ТАБЛИЦЫ ИСТИННОСТИ ФУНКЦИИ К СДНФ
- •ПЕРЕХОД ОТ ТАБЛИЦЫ ИСТИННОСТИ ФУНКЦИИ К СДНФ
- •ПЕРЕХОД ОТ ТАБЛИЦЫ ИСТИННОСТИ
- •Построить логическую схему функции:
- •ПЕРЕХОД ОТ ЛОГИЧЕСКОЙ СХЕМЫ К ФОРМУЛЕ ФУНКЦИИ
- •ТАБЛИЦА ИСТИННОСТИ
- •ПЕРЕХОД ОТ ЛОГИЧЕСКОЙ СХЕМЫ К ФОРМУЛЕ ФУНКЦИИ
- •РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ. ПЕРЕХОД ОТ ЛОГИЧЕСКОЙ СХЕМЫ К ФОРМУЛЕ ФУНКЦИИ
- •РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ. ПЕРЕХОД ОТ ЛОГИЧЕСКОЙ СХЕМЫ К ФОРМУЛЕ ФУНКЦИИ
- •РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ. ПЕРЕХОД ОТ ЛОГИЧЕСКОЙ СХЕМЫ К ФОРМУЛЕ
- •ДВОЙСТВЕННОСТЬ ЛОГИЧЕСКИХ ОПЕРАЦИЙ: ДИЗЪЮНКЦИИ И КОНЪЮНКЦИИ
- •Элементарной дизъюнкцией называется дизъюнкция нескольких переменных и/или их инверсий.
- •Совершенной конъюнктивной нормальной формой (СКНФ ) функции
- •СКНФ функции F (x1, x2, … , xn) можно получить:
- •Построение СКНФ функции по таблице истинности:
- •ПРАВИЛО ПОЛУЧЕНИЯ СКНФ ФУНКЦИИ F С ПОМОЩЬЮ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ
Решение логических задач
1. Выделить из условия задачи элементарные высказывания и обозначить их буквами.
2. Записать условие задачи с помощью логических операций.
3. Составить единое логическое выражение для всех требований задачи.
4. Используя законы алгебры логики, упростить выражение и вычислить его значения либо построить для него таблицу истинности.
5. Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным.
83
6. Проверить, удовлетворяет ли полученное
Пример 17.
На вопрос «Кто из трех студентов изучал логику?», был получен ответ:
«Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?
84
На вопрос «Кто из трех студентов изучал |
||||||
логику?», был получен ответ: |
|
|
||||
«Если изучал первый, то изучал и второй, но |
||||||
неверно, что если изучал третий, то изучал и второй». |
||||||
Кто из учащихся изучал логику? |
|
|
||||
Обозначим: |
|
|
|
|
|
|
Р1 – <логику изучал первый |
||||||
учащийся>, |
|
|
|
|
|
|
Р2 – <логику изучал второй |
|
|||||
учащийся>, |
|
|
|
|
|
|
Р3 – <логику изучал третий |
|
|||||
Упростим выражение |
|
|
||||
учащийся>. |
|
|
|
v Р2) & ( Р3 |
||
(Р1 Р2) & |
(Р3 Р2) = ( Р1 |
|||||
Выражение (Р |
1 |
Р |
) & (Р |
Р ) =1. |
||
v Р2) = |
|
2 |
|
3 |
2 |
|
= ( Р1 v Р2) & Р3 |
& Р = Р1 |
& Р3 & P2v |
||||
Высказывание Р2 & Р2 =0 (правило |
||||||
Р2 & Р3 & |
Р2 |
|
|
|
|
|
операции переменной с ее инверсией), |
||||||
значит: Р2 & Р3 & Р2=0. |
|
|
||||
Поэтому высказывание: Р1 & Р3 & |
||||||
Логику изучал третий учащийся, а первый и |
||||||
Р2=1. |
|
|
|
|
|
85 |
второй не изучали. |
|
|
|
|
Пример 18.
Три подразделения А, В, С фирмы стремились получить максимальную прибыль.
1.Если А получит максимальную прибыль, то В
иС получат максимальную прибыль.
2.Либо А и С получат максимальную прибыль одновременно, либо одновременно не получат.
3.Для того чтобы подразделение С получило максимальную прибыль, необходимо, чтобы
иВ получило максимальную прибыль.
Одно из трех предположений оказалось ложно, а остальные два истинны.
Какие подразделения получили максимальную прибыль?
86
А = {А получит максимальную
прибыль}, В = {В получит максимальную
прибыль}, |
Если А получит максимальную |
|
С = {С получит |
прибыль, то В и С получат |
|
максимальную прибыль. |
|
|
прибыль}. |
максимальную прибыль |
|
|
Либо А и С получат |
|
|
одновременно, либо |
|
1)F1 = А |
одновременно |
|
Для того чтобы подразделение |
||
С получило максимальную |
|
|
2)F2 = А & |
прибыль, необходимо, чтобы и В |
|
получило максимальную |
|
|
3)F3 = С В. |
прибыль. |
|
|
|
|
Одно из трех предположений |
|
|
оказалось ложно, а остальные |
|
|
два истинны. |
87 |
Таблица истинности для F1 |
, F2 |
, F3 |
||||
А |
B |
C |
F1 |
F2 |
|
F3 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
Ответ: В и С получат максимальную прибыль.
88
Таблицы истинности. Обучающая программа «Logic»
89
БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ ЭВМ
90
|
|
|
Использование двоичной |
|
Основные |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
системы представления |
|
|
|
|
|
|
||||||||
|
|
|
данных |
|
принципы |
|
|
|
|
|
|||||||
|
|
|
управления |
|
построени |
|
|
|
|
|
|||||||
|
|
|
Принцип однородности |
|
|
|
|
|
|
||||||||
|
|
|
памяти |
|
|
|
я |
|
|
|
|
|
|||||
|
|
|
программы |
|
архитекту |
|
|
|
|
|
|||||||
|
|
|
Принцип адресности |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
ры |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
ЭВМ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблицы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
истинности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
компьютера, реализующие |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
элементарные логические |
|
|
|
|
|
|
|
|
|
Логические |
|
||||
|
|
функции (И,ИЛИ, НЕ, ИЛИ-НЕ, |
|
|
|
|
|
|
функции |
|
|||||||
|
|
И-НЕ). |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
Аксиомы |
|
|||||||
|
|
Электронные схемы (сумматор, |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
алгебры |
|
||||||||
|
|
|
|
|
|
|
|
||||||||||
|
|
|
Базовые |
|
|
|
|
|
|
|
|
|
|
||||
|
|
триггер). |
|
|
|
|
|
|
|
|
|
логики |
|
||||
|
|
|
логические |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
ные |
|
|||||||
|
|
|
элементы ЭВМ |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Основы |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
логические |
|
||||||
|
|
|
|
|
|
|
алгебры |
|
|
|
91 |
|
|||||
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
операции |
|
|
|
|
|
|
|
|
логики |
|
|
|
|
|
Логические элементы компьютера
Клод |
Шеннон |
впервые |
|
|
|||
доказал |
применимость |
|
|
||||
булевой алгебры в теории |
|
|
|||||
контактных |
и |
релейно- |
|
|
|||
контактных |
схем |
и |
|
|
|||
|
|
||||||
использовал |
ее |
в |
своих |
|
|
||
|
Клод |
|
|||||
работах (1938 г.) |
|
|
|
Шеннон |
(1916 г.)
Логические операции «И», «ИЛИ», «НЕ» лежат в основе работы преобразователей информации любого компьютера.
92