- •Алгоритмы,
- •НАЗНАЧЕНИЯ АЛГОРИТМОВ
- •НЕРАЗМЫШЛЯЮЩИЙ
- •АЛГОРИТМЫ
- •Виды алгоритмов
- •СВОЙСТВА АЛГОРИТМОВ
- •СВОЙСТВА АЛГОРИТМА
- •СВОЙСТВА
- •СВОЙСТВА
- •КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ
- •КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ
- •Начал
- •РАЗРАБОТКА
- •ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ СТРУКТУРЫ АЛГОРИТМА
- •БЛОК-СХЕМА
- •БАЗОВЫЕ КОНСТРУКЦИИ АЛГОРИТМА
- •АЛГОРИТМИЧЕСКИЕ
- •АЛГОРИТМИЧЕСКИЕ
- •АЛГОРИТМИЧЕСКИЕ
- •АЛГОРИТМИЧЕСКИЕ
- •ПРИМЕР
- •Истина
- •БАЗОВЫЕ АЛГОРИТМЫ
- •БАЗОВЫЕ АЛГОРИТМЫ
- •БАЗОВЫЕ АЛГОРИТМЫ
- •Пример.
- •БАЗОВЫЕ АЛГОРИТМЫ
- •Пример. Вычислить сумму 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.
Пусть функция F содержит только операции конъюнкции, дизъюнкции и отрицания. Формулы F и F*
называются двойственными, если формула F* получается из формулы F путем замены в ней каждой операции на двойственную.
Например, для формулы F (x V y) & z двойственной
формулой
Теорема. будет формула F* (x & y) V z. Если формулы А и В равносильны, то
равносильны и им двойственные формулы, то есть А*≡В*.
113
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных и/или их инверсий.
Примеры:
Конъюнктивной нормальной |
|
формой (КНФ) функции А(X, Y, |
|
Z) называется равносильная ей |
|
формула, представляющая собой |
|
конъюнкцию элементарных дизъюнкций |
|
(логическое произведение логических |
|
сумм). |
|
Пример: (X V X V ¬ Y) & (¬X V Z) |
114 |
Совершенной конъюнктивной нормальной формой (СКНФ ) функции
F (x1, x2, … , xn) называется равносильная ей КНФ функции F (x1, x2, … , xn) , обладающая следующими свойствами:
1)каждая элементарная дизъюнкция, входящая в КНФ функции F (x1, x2, … , xn) , содержит все аргументы функции F (x1, x2, … , xn) ;
2)все элементарные дизъюнкции, входящие в КНФ, различны;
3)каждая элементарная дизъюнкция, входящая в КНФ функции F (x1, x2, … , xn), содержит аргумент только один раз;
4)ни одна элементарная дизъюнкция, входящая в КНФ функции F (x1, x2, … , xn) , не содержит одновременно аргумент 115и
СКНФ функции F (x1, x2, … , xn) можно получить:
-с помощью таблицы истинности,
-преобразовать СДНФ, используя закон двойственности,
-с помощью равносильных преобразований.
116
Построение СКНФ функции по таблице истинности:
1.В таблице истинности отметить наборы аргументов, на которых значение функции равно нулю.
2.Составить дизъюнкцию полных конъюнкций, число дизъюнктов равно числу нулевых значений функции.
3.Сопоставить дизъюнкты и отмеченные в п. 1 наборы аргументов: если значение аргумента в наборе равно нулю, то в конъюнкцию включается аргумент, иначе - его инверсия.
117
ПРАВИЛО ПОЛУЧЕНИЯ СКНФ ФУНКЦИИ F С ПОМОЩЬЮ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ
Для функции F получить любую КНФ. Затем помощью равносильных преобразований добиться выполнения свойств совершенной конъюнктивной нормальной формы.
1.Если элементарная дизъюнкция В, входящая в КНФ, не содержит аргумент x1, тогда заменить:
В B V (x1 & x1) (B V x1) & (B V x1).
2.Если КНФ содержит две одинаковые элементарные дизъюнкции, то одну можно исключить, так как B & B B.
3.Если в некоторую элементарную дизъюнкцию В аргумент x1 входит дважды, то лишний нужно исключить, так как:
x1 x1 V x1.
4.Если в элементарную дизъюнкцию входит 118