Логические выражения в информатике примеры как решать и понять?

18 ответов на вопрос “Логические выражения в информатике примеры как решать и понять?”

  1. vulnerating Ответить

    Проверка домашнего задания на уроке осуществляется с помощью авторского теста, разработанного в тестирующей оболочке MyTest (Приложение 1), где проверка теста происходит автоматически (результаты теста сразу отправляются на компьютер учителя).
    В изучении новой темы дается определение простых и сложных высказываний, а также рассматриваются логические операции Объяснение нового материала осуществляется с помощью интерактивной презентации. В целях закрепления умений и навыков учащимся предлагаются карточки для заполнения (Приложение 2).
    В конце урока ученикам предлагается оценить степень удовлетворённости процессом и результатом своей работы и выдаются карточки для выполнения домашнего задания (Приложение 3).
    Учебник под редакцией профессора Н.В. Макаровой «Информатика и ИКТ».
    Цель:
    Изучить теоретический материал по теме «Логические выражения и логические операции»
    Развивать логическое мышление, умение общаться, сопоставлять и применять полученные навыки на практике.
    Развивать познавательную деятельность учащихся, умение анализировать.
    Тип урока: комбинированный урок.
    Формы работы: фронтальная.
    Наглядность и оборудование:
    компьютер;
    мультимедийный проектор;
    презентация, подготовленная в MS PowerPoint;
    тест на тему «Основные понятия алгебры логики»;
    карточки для закрепления пройденного материала;
    карточка для домашней работы.
    План урока:
    Организационный момент (1 мин.)
    Проверка изученного материала (10 мин.)
    Изучение нового материала (20 мин.)
    Закрепление изученного материала (устная работа, 5 мин.)
    Подведение итогов урока (2 мин.)
    Домашнее задание (2 мин.)

    Ход урока

    1. Организационный момент.

    Цель: подготовить учащихся к уроку.
    Объявляется тема урока. Перед учащимися ставится задача: показать, как они научились решать задачи по теме.

    2. Повторение изученного материала.

    Выполнение в тестирующей оболочке MyTest теста на тему «Основные понятия алгебры логики».(приложение1.mtf)
    3. Изучение нового материала.
    Вопросы для изучения:
    Простые и сложные выражения.
    Основные логические операции.
    При объяснении нового материала используется компьютерная презентация (презентация.PPT)
    1. Простые и сложные выражения.
    Логические выражения могут быть простыми и сложными.
    Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».
    Сложное логическое выражение содержит высказывания, объединенные логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания.
    2. Основные логические операции.
    По ходу объяснения нового материала ученики заполняют в тетради таблицу следующего вида.
    Название логической операции
    Обозначение логической операции
    Результат выполнения логической операции
    Таблица истинности
    Примеры
    Отрицание
    Дизъюнкция
    Конъюнкция
    Импликация
    Эквиваленция
    В качестве основных логических операций в сложных логических выражениях используются следующие:
    НЕ (логическое отрицание, инверсия);
    ИЛИ (логическое сложение, дизъюнкция);
    И (логическое умножение, конъюнкция)
    Операция НЕ — логическое отрицание (инверсия)
    Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:
    если исходное выражение истинно, то результат его отрицания будет ложным;
    если исходное выражение ложно, то результат его отрицания будет истинным.
    Для операции отрицания НЕ приняты следующие условные обозначения: НЕ, ?, ? not А. Результат операции отрицания НЕ определяется следующей таблицей истинности.

    Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
    Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами.
    Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
    Результат операции ИЛИ определяется следующей таблицей истинности:
    А
    В
    A v В
    1
    1
    1
    1
    1
    1
    1
    Применяемые обозначения: А или В; A v В; А ог В. При выполнении сложных логических преобразований для наглядности условимся пользоваться обозначением А + В, где А, В — аргументы (исходные высказывания).
    Операция И — логическое умножение (конъюнкция)
    Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение.
    Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
    Результат операции И определяется следующей таблицей истинности:
    А
    В
    А^ В
    1
    1
    1
    1
    1
    Применяемые обозначения: А и В; А ^ В; А & В; A and В.
    Условимся пользоваться при выполнении сложных логических преобразований обозначением A-В, где А, В — аргументы (исходные высказывания).
    Операция «ЕСЛИ-TO» — логическое следование (импликация)
    Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
    Применяемые обозначения:
    если А, то В; А влечет В; if A then В; А—»В.
    Результат операции следования (импликации) ложен, только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
    Таблица истинности:
    А
    В
    Если А, то В
    1
    1
    1
    1
    1
    1
    1
    Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
    Применяемое обозначение: А ~В.
    Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
    Таблица истинности:
    А
    В
    А ~ В
    1
    1
    1
    1
    1
    1
    1

    4. Закрепление изученного материала

    Данный материал раздается каждому ученику. (приложение 2)

    5. Подведение итогов урока

    Скажите был ли сегодняшний урок для вас познавательный?
    Что больше всего запомнилось из урока?

    6. Домашнее задание

    Учебник. п.23.2., заполнить таблицу «Логические операции» до конца.
    Выполнить задание (приложение 3)
    Подготовиться к тестированию.
    Знать ответы на вопросы:
    какие высказывания бывают;
    какие высказывания называются простыми, а какие – сложными;
    основные логические операции и их свойства.

  2. MR_Xaker Ответить

    Внешняя операция выражения — конъюнкция (). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:
    (¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w) = 1 когда:
    1. (¬x ∨ y ∨ z) = 1
    И
    2. (x ∨ ¬z ∨ ¬w) = 1
    Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
    Разобъем исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
    Для сомножителя (¬x ∨ y ∨ z):
    x
    y
    z
    результат
    1
    1
    1
    1
    1
    1
    1
    1
    1
    0
    0
    0
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    Получили ложь в одном наборе, так как дизъюнкция () ложна только тогда, когда ложны все операнды.
    Для сомножителя (x ∨ ¬z ∨ ¬w):
    x
    z
    w
    результат
    1
    1
    1
    1
    1
    0
    1
    1
    0
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
    Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):

    Выпишем только пересеченные наборы:
    x
    y
    z
    w
    F
    1
    1
    1
    1
    1
    1
    1
    1
    Сравнив вторую строку заданной таблицы и вторую строку получившейся таблицы, находим, что x находится в первом столбце.
    x
    y
    z
    w
    F
    1
    1
    1
    1
    1
    1
    1
    1
    x
    ???
    ???
    ???
    F
    1
    1
    0
    1
    1
    1
    1
    1
    1
    Сравнив первую и четвертую одинаковые строки получившейся таблицы, находим, что y в обоих случаях равен 0. Значит он находится в 4-м столбце.
    x
    y
    z
    w
    F
    1
    1
    1
    1
    1
    1
    1
    1
    x
    ???
    ???
    y
    F
    1
    1
    1
    1
    1
    1
    1
    1
    Сравнив предпоследнюю и последнюю строки получившейся таблицы, там где x = 1, находим, что z в обоих случаях равен 0, тогда как w принимает значение и 1 и 0. Значит z находится в 3-м столбце.
    x
    y
    z
    w
    F
    1
    1
    1
    1
    1
    1
    1
    1
    Для w остается второй столбец:
    x
    w
    z
    y
    F
    1
    1
    1
    1
    1
    1
    1
    1
    Результат: xwzy

  3. Adobandis Ответить

    Основная образовательная задача урока – научить учащихся умению упрощать логические выражения, правильно определять порядок выполнения операций в логическом выражении, устанавливать связи между различными частями сложных логических выражений, умение выбирать лучший вариант решения.
    Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
    Обозначим: X – логическое высказывание,  – инверсия, & – конъюнкция,  – дизъюнкция,  – импликация,  – эквиваленция.
    Применение основных законов логики для упрощения логических выражений.
    Представленные примеры демонстрируют основные приемы упрощения логических выражений.
    Упростить логическое выражение:
    1)
    Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций:

    Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией.

    Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией, затем операцией с константами.

    Таким образом,

    2)
    Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных дизъюнкцией. Сначала преобразуем выражения в скобках.

    В первой скобке воспользуемся распределительным законом, во второй скобке – раскроем инверсию по правилу де Моргана и избавимся от инверсии по закону двойного отрицания.

    Воспользуемся операцией переменной с ее инверсией.

    Таким образом,

    3)
    Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных конъюнкцией. Сначала преобразуем выражения в скобках.

    Раскроем инверсию по правилу де Моргана, избавимся от инверсии по закону двойного отрицания.

    Воспользуемся переместительным законом и поменяем порядок логических сомножителей.

    Применим закон склеивания

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

    Таким образом,

    4)
    Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

    В выражении присутствует импликация. Сначала преобразуем импликацию .

    Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.

    Применим закон идемпотенции и перегруппируем логические слагаемые.

    Воспользуемся распределительным законом и вынесем за скобки общий логический множитель.

    Воспользуемся операцией с константами.

    Таким образом,

    5)
    Рассмотрим 3 способа упрощения этого логического выражения.
    1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

    Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией и законом идемпотенции.

    Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией.

    Воспользуемся законом идемпотенции.

    Таким образом,

    2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

    Воспользуемся законом склеивания

    Воспользуемся операцией переменной с ее инверсией.

    Таким образом,

    3 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

    Повторим второй сомножитель , что разрешено законом идемпотенции.

    Сгруппируем два первых и два последних сомножителя.

    Воспользуемся законом склеивания
    Таким образом,

    6)
    Рассмотрим 2 способа упрощения этого логического выражения.
    1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

    Воспользуемся распределительным законом и вынесем общий логический множитель за скобки.

    2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

    Введем вспомогательный логический сомножитель

    Сгруппируем 1 и 4, 2 и 3 логические слагаемые. Вынесем общие логические множители за скобки.

    Воспользуемся операцией с константами и операцией переменной с ее инверсией.

    Таким образом,

    Получили два логических выражения:


    Теперь построим таблицы истинности и посмотрим, правильно ли упрощено логическое выражение




    X
    Y
    Z




    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1

    X
    Y
    Z




    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1

    X
    Y
    Z



    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    X
    Y
    Z



    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1
    1

    Как видно из сравнения таблиц истинности формулы являются равносильными.

  4. Аццкий Талпайоп Ответить

    1. Конъюнкция (логическое умножение) – сложное логическое выражение, которое является истинным только в том случае, когда истинны оба входящих в него простых выражения.
    Обозначение:

    2. Дизъюнкция (логическое сложение) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно, если оба простых логических выражения ложны.
    Обозначение:

    3. Импликация (логическое следствие) – это сложное логическое выражение, которое является ложным тогда и только тогда, когда условие истинно, а следствие ложно.
    Обозначение:

    4. Эквиваленция – это сложное логическое высказывание, которое является истинным только при одинаковых значениях истинности простых выражений, входящих в него.
    Обозначение:

    5. Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.
    Обозначение:

    6. Штрих Шеффера – операция, отрицающая конъюнкцию, т.е. значение ложно тогда и только тогда, когда оба простых выражения истинны.
    Обозначение:

    7. Стрелка Пирса – операция, отрицающая конъюнкцию, т.е. значение истинно тогда и только тогда, когда оба простых выражения ложны.
    Обозначение:

    Порядок выполнения логических операций

    При построении таблицы истинности необходимо учитывать порядок выполнения логических операций:
    Инверсия
    Конъюнкция
    Дизъюнкция
    Импликация
    Эквиваленция
    Штрих Шеффера
    Стрелка Пирса
    Для последних двух операций приоритет не определен.
    Замечание. Если необходимо изменить указанный порядок выполнения логических операций используются скобки.

    Примеры решения задач

  5. Mulhala Ответить

    .
    2.4. Приоритеты логических операций.
    При записи логических выражений, как и при записи алгебраических выражений,          иногда можно не писать скобки При этом соблюдаются следующие договоренности о старшинстве (приоритете) логических операций, первыми указаны операции, которые выполняются в первую очередь:
    отрицание (инверсия),
    конъюнкция (логическое умножение),
    дизъюнкция (логическое сложение),
    импликация (следование),
    тождество.
    Таким  образом,  ¬А \/ В \/ С \/ D  означает  то  же,  что и ((¬А) \/ В)\/ (С \/ D).
    Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна  запись А /\ В /\ С вместо  (А /\ В) /\ С.
    Упражнения.

    3. Свойства логических выражений и таблиц истинности. 

    Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.
    3.1. Общие свойства
    1) Для n логических переменных существует ровно 2n различных наборов значений.
    2) Таблица истинности для логического выражения от n переменных содержит n+1 столбец (по одному столбцу на каждую переменную + 1 столбец на значение выражения) и  2n строк (по одной строке на каждый набор значений переменных).
    3.2.Дизъюнкция
    1) Если хоть одно из выражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
    2) Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
    3) Значение дизъюнкции не зависит от порядка записи выражений, к которым она применяется.
    4) При вычислении дизъюнкции выражений эти выражения можно группировать как угодно – значение дизъюнкции не изменится.
    5) Пусть все выражения, к которым применяется дизъюнкция, – это различные переменные или их отрицания. Тогда существует ровно один набор значений переменных, при которых дизъюнкция ложна. Переменная в этом наборе имеет значение 1, если в дизъюнкцию она входит с отрицанием и значение 0 в противном случае.
    3.3. Конъюнкция
    1) Если хоть одно из выражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
    2) Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
    3) Значение конъюнкции не зависит от порядка записи выражений, к которым она применяется.
    4) При вычислении конъюнкции выражений эти выражения можно группировать как угодно – значение конъюнкции не изменится.
    5) Пусть все выражения, к которым применяется конъюнкция, – это различные переменные или их отрицания. Тогда существует ровно один набор значений переменных, при которых конъюнкция истинна. Переменная в этом наборе имеет значение 1, если в конъюнкцию она входит без отрицания и значение 0 в противном случае.
    3.4. Импликация
    1) Импликация A >B равносильна дизъюнкции (¬А)  \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
    2) Импликация A >B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A>B истинна при любом значении B. Если B=1, то импликация A>B истинна при любом значении A.
    3.5. Эквивалентность
    1) Эквивалентность A ? B равносильна конъюнкции двух импликаций: A>B  и B>A. Эту конъюнкцию можно записать так: (A>B)/\ (B>A)
    2) Эквивалентность A ? B принимает значение 1 (истина) тогда и только тогда, когда значения переменных A и B одинаковы, т.е. A=B=1 или A=B=0.
    Поэтому эквивалентность A ? B равносильна выражению (A/\B) \/ ((¬А) /\ (¬В) ).
    3) Эквивалентность A ? B принимает значение 0 (ложь) тогда и только тогда, когда значения переменных A и B различны, т.е. A=0, а B=1 или A=1, а B=0. Поэтому эквивалентность A ? B равносильна выражению ¬ ( (A/\¬B) \/ (А /\¬В) )
    3.6. Построение выражения с заданной таблицей истинности
    Для любого множества наборов значений переменных можно построить выражение, которое истинно на всех наборах из заданного множества и только на них. Это выражение удобно записать в виде дизъюнкции конъюнкций, причем в каждой конъюнкции (а) каждый член – это простая переменная или ее отрицание и при этом (б) содержатся все переменные.
    Пример. На рисунке приведены все строки таблицы истинности функции F(x, y, z), при которых F(x, y, z) истинно.

    Тогда функция F может быть задана таким выражением:
    (¬x/\y/\z) \/ (x/\¬y/\z) \/ (x/\y/\¬z)
    Здесь первый член дизъюнкции соответствует первой строке таблицы фрагмента истинности; второй член – второй строке; третий член – третьей строке.
    Таким образом, для любой таблицы истинности можно построить логическое выражение с данной таблицей истинности.

    4. Эквивалентные преобразования логических выражений

    4.1. Эквивалентные выражения.
    Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А > В и (¬А) \/ В равносильны, а   А/\В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).
    Эквивалентные выражения имеют одинаковые таблицы истинности, а у неэквивалентных выражений таблицы истинности различны.
    Понятие эквивалентности для логических выражений полностью аналогично понятию эквивалентности для алгебраических выражений.
    4.2. Эквивалентные (тождественные) преобразования выражений.
    Выяснить, эквивалентны ли два выражения, можно сравнив их таблицы истинности. Но это не всегда удобно: построение таблицы истинности – громоздкая задача. Кроме того, часто нужно не просто проверить, эквивалентны ли два данных логических выражения, а построить для данного выражения эквивалентное ему выражение, имеющее заданный вид.  Например, бывает удобно представить выражение в виде дизъюнкции или в виде импликации (см. здесь). Аналогия для алгебраических выражений: разложить на множители выражение x2-y2 (ответ: (x-y)*(x+y) ).
    Замена выражения на другое выражение, эквивалентное ему, называется эквивалентным (синоним: тождественным) преобразованием.
    Основное правило тождественных преобразование – это правило подстановки: если в выражении A  заменить подвыражение P на эквивалентное ему выражение Q, то полученное новое выражение B будет эквивалентно исходному выражению A.
    Правило подстановки работает и для логических, и для алгебраических выражений.
    Пример 1.  Рассмотрим выражение A  = (x>y)?z . Заменим подвыражение P = x>y на эквивалентное ему по определению выражение Q = ¬x?y. Заменяем в A выражение P выражением Q. Получим выражение B = (¬x?y)?z. Выражение B эквивалентно выражению A. Учитывая приоритеты выполнения логических операций, выражение B можно записать и так: ¬x?y?z.
    4.3. Основные логические тождества.
    Между решением задач на эквивалентное преобразование логических и алгебраических выражений есть существенная разница. В алгебре есть устоявшийся список тождественных преобразований выражений. В него входят   формулы, связанные с определением степени и основными законами сложения и умножения (сочетательный, переместительный, распределительный), а также так называемые формулы сокращенного умножения (квадраты и кубы суммы и разности; разность квадратов, сумма и разность кубов). В курсе логики такого общепринятого списка нет.
    В таблице 1 приведен набор логических тождеств (пар эквивалентных логических выражений), которые полезно знать, сдавая ЕГЭ. Это не значит, что другие элементарные тождества вам не понадобится. Мы просто надеемся, что вы сможете при необходимости  вывести другие понадобившиеся тождества. Желательно уметь пользоваться этими формулами так же свободно, как, например, алгебраическими формулами сокращенного умножения. Деление формул в таблице на группы – условное и приведено лишь для удобства восприятия.
    Примечание. В таблицах использована «алгебро-подобная» система обозначений логических операций. Конъюнкция (логическое умножение) и дизъюнкция (логическое сложение) обозначаются символами «·» и «+» соответственно, а отрицание – чертой сверху. Эти обозначения общеприняты среди инженеров (но не специалистов по математической логике :)) и используются в некоторых школьных учебниках, в частности, в учебниках К.Ю.Полякова и Е.А.Еремина
    Таблица 1.

    5. Высказывания о множествах

    Логические выражения над элементарными высказываниями о множествах (высказывания вида “A=?”, “x?A”  “A?B” )  можно преобразовывать, используя не только общие правила преобразования логических выражений, но и свои правила, связанные со свойствами операций над множествами. Ниже U – это универсальное множество; x – его произвольный элемент, A, B, X – множества.  Верны следующие утверждения.
    1. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых x, A, B (это обозначено знаком ?)
    1а) (x?A)?(x?B) ? x?A?B
    1б) (x?A)?(x?B) ? x?A?B
    1в) ¬(x?A) ? x?U\A
    1г)  (x?A)? (¬(x?B)) ? x?A\B
    2. Следующие высказывания эквивалентны, т.е. имеют одинаковые логические значения при любых X, A, B (это обозначено знаком ?)
    2а) (X?A  ?O ) ? (X?B  ?O ) ? (X? (A?B)  ?O )
    2б) (X?A  = O ) ? (X?B  = O ) ? (X? (A?B)  = O )
    3.  (а) Пусть A ? B, т.е.  A – подмножество B; x – элемент универсального множества U. Тогда истинно высказывание:
    (x ? A) > (x? B)
    (б) Пусть высказывание (x ? A) > (x? B)  истинно при любом x ? U. Тогда  A ? B.
    4.  (а) Пусть A ? B, т.е.  A – подмножество B; X ?  U – произвольное множества. Тогда истинно высказывание:
    (X?A  ?O ) > (X?B  ?O )
    (б) Пусть высказывание (X?A  ?O ) > (X?B  ?O )  истинно для любого множества X ?  U. Тогда  A ? B.
    5. Следующее высказывания истинны для любых множеств A, B, X
    ( (X?A  ? O ) ? (X?B  = O ) ) > (X? (A\B)  ?  O )

    6. Примеры эквивалентных преобразований

    Первые два  примера  содержат доказательства свойств импликации из таблицы 1С (см. п.4).
    Пример 1. Преобразуем выражение (¬y)> (¬x)  в выражение x> y.  Имеем:
    1) (¬y) ?  (¬(¬x) )   – замена импликации дизъюнкцией
    2) (¬y) ?  x                – снятие двух отрицаний
    3)   x  > y                   – замена дизъюнкции импликацией
    Пример 2.  Преобразуем выражение  x > (y> z)  в выражение (x?y)> z.  Имеем:
    1) ¬(x?y) ? z                 – замена импликации дизъюнкцией
    2) ( (¬x) ? (¬y) )? z    – правило де Моргана
    3)  (¬x) ? ((¬y) ? z )    – сочетательный закон для дизъюнкции
    4)   (¬x) ? (y  > z )   – замена дизъюнкции импликацией
    5)   x  > (y  > z )      – замена дизъюнкции импликацией
    При анализе высказываний о множествах бывает удобно преобразовывать выражения к импликации, у которой и левый, и правый члены импликации не содержат. Рассмотрим такие примеры.
    Пример 3. Рассмотри выражение (x> y)?  z.  Имеем:
    1) ((¬x) ?  y)?  z  – замена импликации дизъюнкцией
    2) (¬x) ?  (y?  z)  – сочетательный закон для дизъюнкции
    3) x >  (y?  z)  – замена дизъюнкции импликацией
    Пример 4. Рассмотри выражение (x> z) ?  (y> z).  Имеем:
    1) ((¬x) ?  z)  ?  ((¬y) ?  z)   – две замены импликации дизъюнкцией
    2) (¬x) ?  z  ?  (¬y) ?  z        – раскрытие скобок (сочетательный закон для дизъюнкции)
    3) (¬x)  ?  (¬y) ?  z ?  z        – переместительный закон для дизъюнкции
    4) (¬x)  ?  (¬y) ?  z               – закон поглощения для дизъюнкции
    5) ¬(x ? y) ?  z                       – правило де Моргана
    6) (x ? y)  >   z                       – замена дизъюнкции импликацией

  6. Люблю тебя ... Ответить

    Пример 1.

    Для какого из приведённых чисел ложно высказывание:
    НЕ(число > 50) ИЛИ (число чётное)?
    1) 9    2) 56     3) 123     4) 8
    Решение. Сначала выполняем сравнения в скобках, затем операция НЕ, в последнюю очередь – операция ИЛИ.
    1) Подставим число 9 в выражение:
    НЕ (9 > 50) ИЛИ (9 чётное)
    НЕ (ложь) ИЛИ (ложь) = истина ИЛИ ложь = истина
    9 нам не подходит, так как по условию мы должны получить ложь.
    2) Подставим число 56 в выражение:
    НЕ (56 > 50) ИЛИ (56 чётное)
    НЕ (истина) ИЛИ (истина) = ложь ИЛИ истина = истина
    56 тоже не подходит.
    3) Подставим 123:
    НЕ (123 > 50) ИЛИ (123 чётное)
    НЕ (истина) ИЛИ (ложь) = ложь ИЛИ ложь = ложь
    Число 123 подошло.
    Эту задачу можно было решить и по-другому:
    НЕ(число > 50) ИЛИ (число чётное)
    Нам надо получить ложное значение. Мы видим, что операция ИЛИ будет выполняться в последнюю очередь. Операция ИЛИ даст ложь, когда оба выражения НЕ(число) и (число чётное) будут ложны.
    Так как условие (число чётное) должно быть равно ложному значению, то сразу отвергаем варианты с числами 56, 8.
    Далее, условие НЕ (число > 50) = ложь, соответственно условие (число > 50) = истина. Из двух оставшихся чисел 9 и 123 этому условию подходит число 123.
    Итак, можно решать прямой подстановкой, что долго и может дать ошибку при вычислении выражения; или же можно решать задачу быстро, проанализировав все простые условия.
    Ответ: 3)

    Пример 2

    Для какого из приведённых чисел истинно высказывание:
    НЕ(Первая цифра чётная) И НЕ(Последняя цифра нечётная)?
    1) 6843       2)  4562       3) 3561       4) 1234
    Сначала выполняем сравнения в скобках, затем операции НЕ над скобками, в последнюю очередь – операция И. Все это выражение должно принимать истинное значение.
    Так как операция НЕ меняет смысл высказывания на противоположный, мы может переписать это сложное выражение так:
    (Первая цифра нечётная) И (Последняя цифра чётная) = истина
    Как известно, логическое умножение И дает истину только тогда, когда истинны все простые высказывания. Таким образом, оба условия должны быть истинными:
    (Первая цифра нечётная) = истина       (Последняя цифра чётная) = истина
    Как видно, подходит только число 1234
    Ответ: 4)

    Пример 3

    Для какого из приведённых имён истинно высказывание:
    НЕ(Первая буква гласная) И (Количество букв > 5)?
    1) Иван      2) Николай      3) Семён      4) Илларион
    Перепишем выражение:
    (Первая буква не гласная) И (Количество букв > 5) = истина
    (Первая буква согласная)  И (Количество букв > 5) = истина
    Оба условия должны выполняться (команда И дает истину когда оба входящих простых условия истинны).
    Подходит имя “Николай” (первая буква не гласная и число букв 7>5).
    Ответ: 2)

    Пример 4

    Для какого из приведённых значений числа X истинно высказывание:
    НЕ (X > 5) И (X > 4)?
    1) 4     2) 5     3) 6     4) 7
    Первой выполняется операция НЕ, второй – И.
    Перепишем выражение: (X ? 5) И (X > 4) = истина
    Оба условия должны быть верными. Подходит число 5
    Ответ: 2)
    ОГЭ по информатике

  7. СаМаЯ ШиКаРнАя Ответить


    Значение логического выражения.
    Решу ОГЭ. Задание 2

    Логические выражения и логические операции
    Высказывание  — это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности (Аристотель).
    Простым высказыванием  называют повествовательное предложение, относительно которого имеет смысл говорить,  истинно  оно или  ложно (ни одно высказывание не может быть одновременно истинным и ложным).

    Примеры высказываний:
    Москва – столица России. (И)
    Число 27 является простым. (Л)
    Волга впадает в Каспийское море. (И)

    Существуют разные варианты обозначения истинности и ложности логических переменных :
    Истина
    Ложь
    И
    1
    Л
    0

    Логическое выражение
    Логическое выражение  – это символическая запись высказывания, состоящая из  логических величин (констант или переменных) , объединенных  логическими операциями (связками) .
    Связки  “НЕ” инверсия, “И” конъюнкция, “ИЛИ”   дизъюнкция. Это  основные логические операции , при помощи которых можно записать любое логическое выражение.

    Конъюнкция – логическое умножение (от латинского conjunctio – союз, связь)
    Конъюнкция  – это логическая операция, ставящая в соответствие каждым двум простым (или исходным) высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Если хотя бы одно из составляющих высказываний ложно, то и полученное из них с помощью союза  «И»  сложное высказывание также считается ложным.

    Таблица истинности
    Если два высказывания соединены союзом  “И” , то полученное сложное высказывание истинно тогда и только тогда, когда истинны оба исходных высказывания.
    В алгебре множеств  конъюнкции  соответствует операция  пересечения  множеств, т.е. множеству получившемуся в результате умножения множеств  А  и  В  соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.

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

    Таблица истинности
    Если два высказывания соединены союзом  “ИЛИ” , то полученное сложное высказывание истинно когда истинно хотя бы одно из составляющих высказываний.
    В алгебре множеств  дизъюнкции  соответствует операция  объединения  множеств, т.е. множеству получившемуся в результате сложения множеств  А  и  В  соответствует множество, состоящее из элементов, принадлежащих либо множеству  А , либо множеству  В .

    Инверсия  – отрицание (от латинского disjunctio –  разобщение, различие ):
    Отрицание  – логическая операция, которая с помощью связки  «не»  каждому исходному высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

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

    Логическое следование (импликация)
    Высказывание, составленное из двух высказываний при помощи связки  «если …, то …» , называется  логическим следованием, импликацией  (импликация от латинского implico –  тесно связываю ).
    B  “Из А следует В”” width=”640″
    Таблица истинности
    Новое высказывание, полученное с помощью импликации, является ложным тогда и только тогда, когда условие (посылка  А ) – истинно, а следствие (заключение  В ) – ложно и истинно во всех остальных случаях.В алгебре множеств  логическому отрицанию  соответствует операция  дополнения  до универсального множества, т.е. множеству получившемуся в результате отрицания множества  А  соответствует множество, дополняющее его до универсального множества.
    A = B  “Из А следует В”

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

    Таблица истинности
    Новое высказывание, полученное с использованием эквивалентности, является истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
    A  B “А равносильно В”

    Примеры решения задач Демо версия ОГЭ 2016
    Ответ 1

  8. Malorius Ответить

    Урок по информатике рассчитан на
    учащихся 10-х классов общеобразовательной школы, в учебном плане которой входит
    раздел «Алгебра логики». Учащимся очень нелегко дается эта тема, поэтому мне,
    как учителю, захотелось заинтересовать их в изучении законов логики, упрощении
    логических выражений и с интересом подойти к решению логических задач. В
    обычной форме давать уроки по этой теме нудно и хлопотно, да и ребятам не
    всегда понятны некоторые определения. В связи с предоставлением информационного
    пространства, у меня появилась возможность выкладывать свои уроки в оболочке
    «learning». Учащиеся, зарегистрировавшись в ней, могут в свое свободное время
    посещать этот курс и перечитывать то, что было непонятно на уроке. Некоторые
    учащиеся, пропустив уроки по болезни, наверстывают дома или в школе пропущенную
    тему и всегда готовы к следующему уроку. Такая форма преподавания очень
    устроила многих ребят и те законы, которые им были непонятны, теперь в
    компьютерном виде ими усваиваются гораздо легче и быстрее. Предлагаю один из
    таких уроков информатики, который проводится интегративно с ИКТ.
    План урока
    Объяснение нового материала, с привлечением компьютера –
    25 минут.
    Основные понятия и определения, выложенные в «learning»
    – 10 минут.
    Материал для любознательных – 5 минут.
    Домашнее задание – 5 минут.
    1. Объяснение нового материала
    Законы формальной логики
    Наиболее простые
    и необходимые истинные связи между мыслями выражаются
    в основных законах формальной логики. Таковыми являются законы тождества,
    непротиворечия, исключенного третьего, достаточного основания.
    Эти законы
    являются основными потому, что в логике они играют особо важную роль, являются
    наиболее общими. Они позволяют упрощать
    логические выражения и строить умозаключения и доказательства. Первые три из вышеперечисленных законов были
    выявлены и сформулированы
    Аристотелем, а закон достаточного основания — Г. Лейбницем.
    Закон тождества: в процессе определенного
    рассуждения всякое понятие и суждение должны быть тождественны самим
    себе.

    Закон непротиворечия: невозможно, чтобы одно и то
    оке в одно то же время было и не было
    присуще одному и тому же в одном и том же
    отношении. То есть невозможно что-либо одновременно утверждать и
    отрицать.

    Закон исключенного третьего: из двух
    противоречащих суждений одно истинно, другое ложно, а третьего не дано.

    Закон достаточного основания: всякая истинная
    мысль должна быть достаточно обоснована.

    Последний закон говорит о том, что доказательство
    чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же
    мысли доказать нельзя. Есть хорошая
    латинская пословица: «Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу».
    Формулы этого закона нет, так как он имеет только содержательный характер. В
    качестве аргументов для подтверждения истинной мысли могут быть использованы истинные суждения,
    фактический материал, статистические
    данные, законы науки, аксиомы, доказанные теоремы.
    Законы алгебры высказываний
    Алгебра
    высказываний (алгебра логики) — раздел математической логики, изучающий логические операции над высказываниями и правила преобразования
    сложных высказываний.
    При решении многих логических задач часто
    приходится упрощать формулы, полученные при формализации их условий.
    Упрощение формул в алгебре высказываний
    производится на основе эквивалентных преобразований, опирающихся на
    основные логические законы.
    Законы алгебры высказываний (алгебры логики) — это тавтологии.
    Иногда эти законы называются
    теоремами.
    В алгебре
    высказываний логические законы выражаются в виде равенства эквивалентных формул.
    Среди законов особо выделяются такие,
    которые содержат одну переменную.
    Первые четыре из
    приведенных ниже законов являются основными законами алгебры высказываний.
    Закон тождества:
    А=А
    Всякое
    понятие и суждение тождественно самому себе.
    Закон тождества означает, что в процессе
    рассуждения нельзя подменять одну
    мысль другой, одно понятие другим. При нарушении этого закона возможны
    логические ошибки.
    Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно,
    так как первое и второе слова «язык» обозначают разные понятия.
    В рассуждении: Движение вечно.
    Хождение в школу — движение. Следовательно,
    хождение в школу вечно
    слово
    «движение» используется в двух разных смыслах (первое — в философском смысле —
    как атрибут материи, второе — в обыденном смысле — как действие по
    перемещению в пространстве), что приводит к
    ложному выводу.
    Закон непротиворечия:

    Не
    могут быть одновременно истинными суждение и его отрицание. То есть если высказывание А — истинно, то
    его отрицание не А должно быть
    ложным (и наоборот). Тогда их произведение будет всегда ложным.
    Именно это равенство часто используется при
    упрощении сложных логических выражений.
    Иногда этот закон формулируется так: два противоречащих
    друг другу высказывания не могут быть
    одновременно истинными. Примеры невыполнения закона непротиворечия:
    1. На Марсе есть жизнь и на Марсе жизни нет.
    2. Оля окончила среднюю
    школу и учится в X классе.

    Закон исключенного третьего:

    В один и тот же момент времени высказывание может
    быть либо истинным, либо ложным,
    третьего не дано. Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего:
    1. Число 12345 либо четное, либо нечетное, третьего
    не дано.

    2. Предприятие работает убыточно
    или безубыточно.

    3. Эта жидкость является или
    не является кислотой.

    Закон исключенного третьего не является законом,
    признаваемым всеми логиками в качестве универсального закона логики. Этот закон
    применяется там, где познание имеет
    дело с жесткой ситуацией: «либо — либо»,
    «истина—ложь». Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон
    исключенного третьего часто не может быть применен.
    Рассмотрим следующее высказывание: Это
    предложение ложно.
    Оно не может быть
    истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не
    ложно, а потому нарушается закон исключенного третьего.
    Парадокс (греч. paradoxos — неожиданный, странный) в этом примере возникает из-за того, что предложение
    ссылается само на себя. Другим
    известным парадоксом является задача о парикмахере: В одном городе
    парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы
    парикмахеру?
    В логике из-за ее
    формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики
    нельзя выразить все возможные мысли и доводы. Покажем, как на основании определения эквивалентности высказываний могут
    быть получены остальные законы алгебры высказываний.
    Например, определим, чему эквивалентно
    (равносильно) А (двойное
    отрицание А, т. е. отрицание отрицания А). Для этого построим таблицу
    истинности:

    По определению равносильности мы должны найти тот
    столбец, значения которого совпадают со значениями столбца А. Таким будет
    столбец А.
    Таким образом, мы можем сформулировать закон
    двойного
    отрицания:

    Если отрицать дважды некоторое высказывание, то в
    результате получается исходное высказывание. Например, высказывание А = Матроскин кот эквивалентно
    высказыванию А = Неверно, что Матроскин не кот.
    Аналогичным
    образом можно вывести и проверить следующие законы:
    Свойства констант:

    Законы идемпотентности:

    Сколько бы раз мы ни повторяли: телевизор
    включен или телевизор включен или телевизор включен …
    значение
    высказывания не изменится. Аналогично от повторения на улице тепло,
    на улице тепло,…
    ни на один градус теплее не станет.
    Законы коммутативности:
    A v B = B v A
    А
    & В = В & А

    Операнды А и
    В в операциях дизъюнкции и конъюнкции можно менять местами.
    Законы ассоциативности:
    A v(B v C) = (A v B) v C;
    А & (В
    & C) = (A &
    В) & С.

    Если в выражении
    используется только операция дизъюнкции или только операция конъюнкции, то
    можно пренебрегать скобками или произвольно их расставлять.
    Законы дистрибутивности:
    A v (B & C) = (A v B) &(A v C)
    (дистрибутивность дизъюнкции
    относительно конъюнкции)

    А & (B v C) = (A & B) v (А & C)
    (дистрибутивность конъюнкции
    относительно дизъюнкции)

    Закон
    дистрибутивности конъюнкции относительно
    дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон
    дистрибутивности дизъюнкции относительно
    конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее
    всего провести с помощью таблицы истинности:

    Законы поглощения:
    A v (A & B) = A
    A & (A v B) = A
    Проведите
    доказательство законов поглощения самостоятельно.
    Законы де Моргана:


    Словесные формулировки законов де Моргана:
    1.

    2.

    Мнемоническое правило: в левой части тождества операция отрицания
    стоит над всем высказыванием. В правой части она как бы разрывается и отрицание
    стоит над каждым из простых высказываний, но одновременно меняется операция:
    дизъюнкция на конъюнкцию и наоборот.
    Примеры выполнения закона де Моргана:
    1) Высказывание Неверно, что
    я знаю арабский или китайский язык
    тождественно высказыванию Я не
    знаю арабского языка и не знаю китайского языка.

    2) Высказывание Неверно, что я выучил урок и
    получил по нему двойку
    тождественно высказыванию Или я не выучил урок,
    или я не получил по нему двойку.

    Замена операций импликации и
    эквивалентности

    Операций импликации и эквивалентности иногда нет
    среди логических операций конкретного
    компьютера или транслятора с языка программирования. Однако для решения многих задач эти операции необходимы. Существуют
    правила замены данных операций на последовательности операций отрицания,
    дизъюнкции и конъюнкции.
    Так, заменить операцию импликации можно в
    соответствии со следующим правилом:

    Для замены операции эквивалентности
    существует два правила:

    В справедливости данных формул легко убедиться,
    построив таблицы истинности для правой и левой частей обоих тождеств.
    Знание правил замены операций импликации и
    эквивалентности помогает, например, правильно построить отрицание
    импликации.
    Рассмотрим
    следующий пример.
    Пусть дано высказывание:
    Е = Неверно, что если я выиграю конкурс, то получу приз.
    Пусть А = Я выиграю
    конкурс,

    В = Я получу приз.
    Тогда

    Отсюда, Е = Я выиграю конкурс, но приз не получу.
    Интерес
    представляют и следующие правила:

    Доказать
    их справедливость можно также с помощью таблиц истинности.
    Интересно
    их выражение на естественном языке.
    Например, фраза
    Если Винни-Пух съел мед, то он
    сыт

    тождественна фразе
    Если Винни-Пух не сыт, то меда
    он не ел.

    Задание: придумайте
    фразы-примеры на данные правила.
    2. Основные понятия и определения в Приложении 1
    3. Материал для любознательных в Приложении 2
    4. Домашнее задание
    1) Выучить законы логики, используя курс «Алгебры логики», размещенный в
    информационном пространстве (www.learning.9151394.ru).
    2) Проверить
    на ПК доказательство законов де Моргана, построив таблицу истинности.
    Приложения
    Основные понятия и определения
    (Приложение 1).
    Материал для любознательных
    (Приложение 2).

  9. VideoAnswer Ответить

Добавить комментарий для СаМаЯ ШиКаРнАя Отменить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *