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

Решение логических выражений принято записывать в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.

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

      1. действия в скобках,
      2. инверсия (отрицание ),
      3. & (конъюнкция ),
      4. v (дизъюнкция ),
      5. => (импликация ),
      6. <=> (эквивалентность ).

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

1. Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных + строка заголовков столбцов).

2. Выяснить количество столбцов (вычисляется как количество переменных + количество логических операций).

3. Установить последовательность выполнения логических операций.

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

5. Заполнить таблицу истинности по столбцам.

6. Записать ответ.

Пример 6

Построим таблицу истинности для выражения F =(Av B )&(¬ A v ¬ B ) .

1. Количество строк=2 2 (2 переменных+строка заголовков столбцов)=5.

2. Количество столбцов=2 логические переменные (А, В)+ 5 логических операций (v ,&, ¬ , v , ¬ ) = 7.

3. Расставим порядок выполнения операций: 1 5 2 43

(A v B ) & (¬ A v ¬ B )

4-5. Построим таблицу и заполним ее по столбцам:

А v В

¬ А

¬ В

¬ А v ¬ В

(A v B )&(¬ A v ¬ B )

0

0

0

1

1

0

6. Ответ: F =0, при A= B=0 и A= B=1

Пример 7

Построим таблицу истинности для логического выражения F = X v Y & ¬ Z .

1. Количество строк=2 3 +1=(3 переменных+строка заголовков столбцов)=9.

2. Количество столбцов=3 логические переменные+3 логических операций = 6.

3. Укажем порядок действий: 3 2 1

X v Y & ¬ Z

4-5. Построи м таблицу и заполним ее по столбцам:

¬ Z

Y& ¬ Z

Xv Y & ¬ Z

0

0

0

0

0

0

1

0

6. Ответ:

F =0, при X= Y= Z= 0; при X= Y=0 и Z= 1.

Упражнение 8

Постройте таблицы истинности для следующих логических выражений:

1. F =(Av B )&(¬ A& ¬ B).

2. F = X&¬ Yv Z.

Проверьте себя (эталон ответов)

Обратите внимание!

Наборы входных переменных, во избежание ошибок, рекомендуется перечислять следующим образом:

А) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

Б) разделить колонкузначенийвторой переменной на четыре части и заполнить каждую четверть чередующимися группами нулей и единиц, начиная с группы нулей;

В) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами нулей или единиц до тех пор, пока группы нулей и единиц не будут состоять из одного символа.

Тавтология - тождественно истинная формула истина " ("1

Противоречие - тождественно ложная формула , или формула принимающая значение "ложь " ("0 ") при любых входящих в нее значениях переменных.

Равносильные формулы - две формулы А и В принимающие одинаковые значения, при одинаковых наборах значений входящих в них переменных. Равносильность двух формул алгебры логики обозначается символом .

Страница 1

Урок информатики по теме "Основы логики, таблицы истинности"

Тема: Как построить таблицу истинности?

Продолжительность урока: 40 мин

Тип урока: комбинированный:


  • проверка знаний – устная работа;

  • новый материал – лекция;

  • закрепление – практические упражнения;

  • проверка знаний – задания для самостоятельной работы.
Цели урока:

  1. Обучающие:

    1. Научить составлять логические выражения из высказываний

    2. Ввести понятие “таблица истинности”

    3. Изучить последовательность действий построения таблиц истинности

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

  2. Развивающие:

    1. Развивать логическое мышление

    2. Развивать внимание

    3. Развивать память

    4. Развивать речь учащихся

  3. Воспитательные:

    1. Воспитывать умение слушать учителя и одноклассников

    2. Воспитывать аккуратность ведения тетради

    3. Воспитывать дисциплинированность
План урока:

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

  2. Повторение материала предыдущего урока +проверка домашнего задания (устный опрос) (5 мин).

  3. Объяснение нового материала (10 мин).

  4. Физкультминутка (1 мин).

  5. Закрепление

    • разбор примера (5 мин);

    • практические упражнения (10 мин);

    • задания для самостоятельной работы (5 мин).

Оборудование и программный материал:

  • белая доска;

  • раздаточный справочный материал “Таблицы истинности”;

  • демонстрация презентации “Таблицы истинности”.
Ход урока

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


  • Приветствие.

  • Проверка отсутствующих в классе.

  • Объявление оценок за прошлый урок.
2. Повторение материала предыдущего урока + проверка домашнего задания

3 учащихся работают по карточкам:

Соедините правильные определения или обозначения:


1. Логика

1.

2. Высказывание

2. Логическое сложение

3. Алгебра логики

3. Наука о формах и способах мышления

4. Логическая переменная

4. Логическое отрицание

5. Дизъюнкция

5. ИСТИНА и ЛОЖЬ

6. Инверсия

6.


7. Конъюнкция

7.

8. Импликация

8. Наука об операциях над высказываниями

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

9. Повествовательное предложения, в котором что-либо утверждается или отрицается, которое может быть истинным или ложным

Остальные устно.

1)Примеры записаны на доске:


  1. Для логических выражений сформулируйте составные высказывания на обычном языке:
А) (Y>1 и Y 4) (Ответ: число Y принадлежит промежутку (1,3) и (4,8))

Б) (X=Y) и (X=Z). (Ответ: числа X , Y и Z равны между собой)

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

Какие логические связки вы использовали? (Инверсия, дизъюнкция и конъюнкция)

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

Давайте вспомним основные определения и понятия:

3. Объяснение нового материала

Из составного высказывания составьте формулу, заменяя простые высказывания переменными.

Задача: В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого не делал, так как в это время сдавал мне зачет. Следовательно, это сделал Коля.

Решение: Формализуем данное сложное высказывание:

К – это сделал Коля; С – это сделал Саша.

Форма высказывания:

На прошлом уроке мы находили значение составного высказы­вания путем подстановки исходных значений входящих логических переменных. А сегодня мы узнаем, что можно построить таблицу истинности, которая определяет истинность или лож­ность логического выражения при всех возможных комбинациях исходных значе­ний простых высказываний (логических переменных) и, что можно определить значения исходных логических переменных, зная какой нам нужен результат.

Итак, тема сегодняшнего урока: «Как построить таблицу истинности?»

Мы уже несколько уроков подряд используем понятие “таблица истинности”? так что же такое таблица истинности ?

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

Еще раз рассмотрим наш пример

и построим таблицу истинности для этого составного высказывания

При построении таблиц истинности есть определенная последовательность действий. Давайте запишем


  1. Необходимо определить количество строк в таблице истинности.

  • количество строк = 2 n , где n – количество логических переменных

  1. Необходимо определить количество столбцов в таблице истинности.

  • количество столбцов = количеству логических переменных + количество логических операций.

  • Необходимо построить таблицу истинности с указанным количеством строк и столбцов, ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов (¬, &, V);

  1. Заполнить столбцы входных переменных наборами значений

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

К

С












0

0

1

0

0

1

0

1

0

1

0

1

1

0

1

1

1

1

1

1

0

1

0

1

4. Физкультминутка


      1. Закрепление

  • разбор примера.

  • практические упражнения.

  • задания для самостоятельной работы.
Построить таблицы истинности для таких составных высказываний:

А)



А

В







0

0

0

1

0

1

0

0

1

0

0

0

1

1

1

0

Б)



А

В










0

0

1

0

1

0

1

0

1

0

1

0

1

1

1

1

1

0

1

0

В)



А

В

С










0

0

0

1

0

0

0

0

1

1

1

1

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

1

0

1

1

0

1

1

1

1

1

1

0

0

0

1

1

1

1

0

0

1

Задание для самостоятельной работы «Кто быстрей?»

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



А

В

С



Ответ:


А

В

С











0

0

0

1

0

1

0

0

0

1

0

0

0

1

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

0

0

1

0

1

0

1

0

1

0

0

0

1

1

1

0

1

1

1

0

1

1

1

0

1

1

0

      1. Обобщение урока, домашнее задание (2 мин).
На этом уроке мы закрепили понятие «таблицы истинности», познакомились с алгоритмом построения таблиц истинности, а также научились строить их для составных высказываний, не вникая в смысл самого высказывания.

Д/З не задается, так как урок спаренный, дети приходят через урок и продолжаем изучать тему «Основы логики и логические основы компьютера».

страница 1

В цифровой схемотехнике цифровой сигнал - это сигнал, который может принимать два значения, рассматриваемые как логическая "1" и логический "0".

Логические схемы могут содержать до 100 миллионов входов и такие гигантские схемы существуют. Представьте себе, что булева функция (уравнение) такой схемы была потеряна. Как восстановить её с наименьшими потерями времени и без ошибок? Наиболее продуктивный способ - разбить схему на ярусы. При таком способе записывается выходная функция каждого элемента в предыдущем ярусе и подставляется на соответствующий вход на следующем ярусе. Этот способ анализа логических схем со всеми нюансами мы сегодня и рассмотрим.

Логические схемы реализуются на логических элементах: "НЕ", "И", "ИЛИ", "И-НЕ", "ИЛИ-НЕ", "Исключающее ИЛИ" и "Эквивалентность". Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе . Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).

На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.

Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.

Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:

  • трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
  • четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).

Рассмотрим построение (синтез) логических схем

  • в булевом базисе "И", "ИЛИ", "НЕ" (в предпоследнем параграфе);
  • в также распространённых базисах "И-НЕ" и "ИЛИ-НЕ" (в последнем параграфе).

Задача анализа логических схем

Задача анализа заключается в определении функции f , реализуемой заданной логической схемой. При решении такой задачи удобно придерживаться следующей последовательности действий.

  1. Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
  2. Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра - номер яруса, а остальные цифры - порядковый номер элемента в ярусе.
  3. Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
  4. Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.

Пример 1.

Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:

x , y , z :

x y z f
1 1 1 0 1 1 1 1
1 1 0 0 0 0 1 0
1 0 1 0 0 0 1 0
1 0 0 0 0 0 1 0
0 1 1 0 0 0 1 0
0 1 0 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 1 0 1 0 0

Пример 2. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Пример 3. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.


Продолжаем искать булеву функцию логической схемы вместе

Пример 4. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x , y , z :

В итоге получим функцию, которую реализует на выходе логическая схема:

.

Таблица истинности для данной логической схемы:

x y z f
1 1 1 0 1 1
1 1 0 0 1 1
1 0 1 1 0 1
1 0 0 0 0 0
0 1 1 0 1 1
0 1 0 0 1 1
0 0 1 0 1 1
0 0 0 0 1 1

Пример 5. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная - самая нижняя - пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x , y , z :

В итоге получим функцию, которую реализует на выходе логическая схема:

.

Таблица истинности для данной логической схемы:

x y z f
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 0 1
1 0 0 1 0 1
0 1 1 1 1 1
0 1 0 1 1 1
0 0 1 1 0 1
0 0 0 1 0 1

Задача синтеза логических схем в булевом базисе

Разработка логической схемы по её аналитическому описанию имеет название задачи синтеза логической схемы.

Каждой дизъюнкции (логической сумме) соответствует элемент "ИЛИ", число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент "И", число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент "НЕ".

Часто разработка логической схемы начинается с определения логической функции, которую должна реализовать логическая схемы. В этом случае дана только таблица истинности логической схемы. Мы разберём именно такой пример, то есть, решим задачу, полностью обратную рассмотренной выше задаче анализа логических схем.

Пример 6. Построить логическую схему, реализующую функцию с данной таблицей истинности.

Построение таблиц истинности и логических функций

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a , b ).

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

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

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквивалентность.

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

Алгоритм построения таблиц истинности для сложных выражений :

количество строк = 2 n + строка для заголовка ,

n - количество простых высказываний.

количество столбцов = количество переменных + количество логических операций ;

· определить количество переменных (простых выражений);

· определить количество логических операций и последовательность их выполнения.

3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.

Пример: Составить таблицу истинности логического выражения:

D = А & ( B V C )

Решение:

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n =3 и количество строк = 23 +1 = 9.

2. Определить количество столбцов:

простые выражения (переменные): А, В, С ;

промежуточные результаты (логические операции):

А - инверсия (обозначим через E );

B V C - операция дизъюнкции (обозначим через F );

а также искомое окончательное значение арифметического выражения:

D = А & ( B V C ) . т. е. D = E & F - это операция конъюнкции.

Заполнить столбцы с учетом таблиц истинности логических операций.

font-size:12.0pt">Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z (X ,Y ):

font-size:12.0pt">1 .

Так как строки две, получаем дизъюнкцию двух элементов: () V () .

Каждый логический элемент в этой дизъюнкции запишем в виде конъюнкции аргументов функции X и Y : ( X & Y ) V ( X & Y ).

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

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

При построении таблицы истинности необходимо учитывать порядок выполнения логических операций. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:

  • 1. инверсия;
  • 2. конъюнкция;
  • 3. дизъюнкция;
  • 4. импликация и эквивалентность.

Для изменения указанного порядка выполнения логических операций используются круглые скобки.

Предлагается следующий алгоритм построения таблицы истинности .

  • 1. Определить количество наборов входных переменных - всевозможных сочетаний значений переменных, входящих в выражения, по формуле: Q=2 n , где n - количество входных переменных. Оно определяет количество строк таблицы.
  • 2. Внести в таблицу все наборы входных переменных.
  • 3. Определить количество логических операций и последовательность их выполнения.
  • 4. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.

Чтобы не повторить или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.

Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор - число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор - максимальное значение двоичного числа для данной длины кода.

Например, для функции от трех переменных последовательность наборов состоит из чисел:

Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:

  • а) разделить колонку значений первой переменной пополам и заполнить верхнюю половину нулями, нижнюю половину единицами;
  • б) в следующей колонке для второй переменной половинку снова разделить пополам и заполнить группами нулей и единиц; аналогично заполнить вторую половинку;
  • в) так делать до тех пор, пока группы нулей и единиц не будут состоять из одного символа.

Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:

Например, построим таблицу истинности для логической функции:

Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов Q=2 3 =8 .

Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и (B V C ), а также искомого окончательного значения сложного арифметического выражения:

  • 0 0 0 1 0 0
  • 0 0 1 1 1 1
  • 0 1 0 1 1 1
  • 0 1 1 1 1 1
  • 1 0 0 0 0 0
  • 1 0 1 0 1 0
  • 1 1 0 0 1 0
  • 1 1 1 0 1 0
  • 7.4. Логические функции и их преобразования. Законы логики

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

Законы логики

  • 1. ¬¬ А
  • 2. A&B
  • 3. AVB
  • 4. A&(B&C)
  • 5. AV(BVC)
  • 6. A&(BVC)
  • 7. AV(B&C)
  • 8. A&A
  • 9. AVA
  • 10. AV¬A
  • 11. A&¬A
  • 12. A&И
  • 13. AVИ
  • 14. A&Л
  • 15. AVЛ
  • 16. ¬(A&B)
  • 17. ¬(AVB)
  • 18. A => B

Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

Пример 1. Упростить выражения так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.

Решение

Пример 2. Минимизировать функцию

При упрощении выражения использовались формулы поглощения и склеивания.

Пример 3. Найти отрицание следующего высказывания: "Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно".

Решение

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

Y - "Урок интересный";

M - "Миша смотрит в окно";

B - "Вика смотрит в окно";

C - "Света смотрит в окно".

При упрощении выражения использовались формула замены операций и закон де Моргана.

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

  • 1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";
  • 2) "Если Иванов не участвовал, то Сидоров не участвовал".

Решение

Составим выражения:

I - "Иванов участвовал в преступлении";

P - "Петров участвовал в преступлении";

S - "Сидоров участвовал в преступлении".

Запишем посылки в виде формул:

Проверим результат, используя таблицу истинности:


Ответ: Иванов участвовал в преступлении.

Построение логической функции по ее таблице истинности

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

Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).

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

Z(X,Y) <=> ((¬X& ¬Y) VX)&((¬X&Y)V ¬Y) <=> (XV(¬X& ¬Y)) &(¬YV(¬X&¬Y)) <=> ((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y)) <=> (1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=> (XV ¬Y)&((¬YV ¬X)& ¬Y).

Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y).

Запишите правила конструирования логической функции по ее таблице истинности:

  • 1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
  • 2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
  • 3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
  • 4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.

Новые статьи

Популярные статьи

© 2024 x360ce.ru
Фотография - Информационный портал