Построение таблиц истинности — в помощь студенту

  • Департамент образования Ивановской области
  • ОГБПОУ «Кинешемский педколледж»
  • Построение таблиц истинности
  • Методическое пособие

Подготовила: Совина М.В.

преподаватель высшей категории

2015

М.В. Совина

Методическое пособие «Построение таблиц истинности»- Кинешма, 2015

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

Содержание

Алгебра логики………………………………………………………………… 4
Логические операции…………………………………………………………. 5
Этапы построения таблиц истинности……………………………………… 9
Пример построения таблиц истинности……………………………………. 10
Задания для самоконтроля…………………………………………………… 12
Рекомендуемая литература…………………………………………………… 13

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

Логикаэто наука о формах и способах мышления. Логика позволяет строить формальные модели окружающего мира.

  1. Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основесовременной логики лежат учения, созданные древнегреческими
  2. мыслителями.
  3. Основными формами мышления являются: понятие, высказывание, умозаключение.
  4. Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.

Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо ИСТИННО либо ЛОЖНО.

  • Умозаключение — это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение
  • Основы формальной логики заложил Аристотель.
  • Алгебра логики была разработана для того, чтобы можно былооперировать высказываниями, не вникая в их содержание.
  • Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.
  • Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй.
  • Логические операции
  • Простые высказывания обозначаются латинскими буквами: А, В, С …
  • Bысказывания, образованные из других высказываний с помощью логических связок, называются составными.

Употребляемые в обычной речи слова и словосочетания «не”, “и”, “или”, “если… , то”, “тогда и только тогда” и другие позволяют из простых высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

  1. Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.
  2. Пусть через А обозначено высказывание “Тимур поедет летом на море”,
  3. а через В — высказывание “Тимур летом отправится в горы”.
  4. А, В — логические переменные, каждое из которых мoжет принимать только два значения — “истина” или “ложь”, обозначаемые, соответственно, “1” или “0”.
  5. Составное высказывание “Тимур летом побывает на море и в горах” можно кратко записать как А и В.
  6. Здесь “и” — логическая связка.
  7. Составное высказывание “Тимур летом побывает на море или в горах” можно кратко записать как А или В.
  8. Здесь “или” — логическая связка.
  9. Истинность или ложность получаемых составных высказываний зависит от истинности или ложности элементарных высказываний.
  10. В алгебре логики в соответствии с логическими связками используют 5 базовых логические операций: конъюнкция, дизъюнкция, инверсия, импликация и эквивалентность. Для каждой из операций составлены таблицы истинности
  11. Таблица истинности логической операции выражает соответствие между всевозможными наборами значений исходных данных, переменными и значениями, получаемыми в результате выполнения операции.

Построение таблиц истинности - в помощь студенту Построение таблиц истинности - в помощь студенту Построение таблиц истинности - в помощь студенту Построение таблиц истинности - в помощь студенту Построение таблиц истинности - в помощь студенту

Приоритеты логических операций:

  • инверсия (отрицание),
  • конъюнкция (логическое умножение),
  • дизъюнкция (логическое сложение),
  • импликация (следование),
  • эквивалентность (равносильность).
  • Изменить последовательность выполнения логических операций можно с помощью скобок.
  • Этапы построения таблиц истинности
  • Решение логических выражений принято записывать в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.
  • Для составления таблицы необходимо:
  1. Выяснить количество строк в таблице. Оно равно 2n+1, где n-количество переменных.

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

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

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

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

  1. Заполнение столбцов значений переменных таблицы:
  2. 1.  разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;
  3. 2.  разделить колонку  значений  второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3.  продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Заполнение столбцов, содержащих логические операции, выполняется в соответствии с таблицами истинности этих логических операций

Примеры построения таблиц истинности

Читайте также:  Расселение восточных славян к viii веку - в помощь студенту

Пример 1. Для формулы  A/ (B / ¬B /¬C) постройте  таблицу истинности.

  • 1этап:  Количество логических переменных 3, следовательно, количество строк — 23 +1= 9.
  • 2 этап: Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.
  • 3этап: Последовательность операций:
  • 1) ¬B
  • 2) ¬C
  • 3)  ¬B /¬C
  • 4) B / ¬B /¬C
  • 5) A/ (B / ¬B /¬C)
  • 4 этап: Построение таблицы
A B C ¬B ¬C ¬B¬C B¬B¬C A(B¬B¬C)

5 этап: Заполнение таблицы

Построение таблиц истинности - в помощь студенту

Пример 2. Определите истинность  логического выражения  

F(А, В) = (А/ В)/(¬А/¬В) .

1. В выражении две переменные А и В (n=2).

2.  mстрок=2n, m=22=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А/ В;  2) ¬А;  3) ¬В;  4) ¬А/¬В;  5) (А/ В)/(¬А/¬В).

5. Кстолбцов=n+5=2+5=7 столбцов.

А В А/ В ¬А ¬В ¬А/¬В F
0 0 0 1 1 1
0 1 1 1 0 1 1
1 0 1 0 1 1 1
1 1 1 0 0 0

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Задания для самоконтроля

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

A  B (A  B)

  1. Определите истинность  логического выражения :

F(А,В) =A  B  C  A

  1. Постройте таблицу истинности сложного высказывания

А V (A ^ B) V (B ^ C)

  1. Составить таблицу истинности для формулы

X·Y v X v Y v X

  1. Составить таблицу истинности для формулы

Рекомендуемая литература

  1. Андреева Е.В. Математические основы информатики. Элективный курс: учебное пособие.-М.:БИНОМ. Лаборатория знаний, 2005

  2. Выгодский М.Я. Справочник по элементарной математике. М. «Наука»,1989.

  3. Соколова О.А. Универсальные поурочныеразработки по информатике 10 класс:- М.:ВАКО,2008, -400с.

  4. Угринович Н. Информатика и ИТ 10-11- М.:Лаборатория Базовых Знаний,2001. – 464с.

  5. Щеглов А.И. Элементарное введение в теорию множеств и алгебру логики. Иваново, 1978.

  6. Математическая логика.- Режим доступа: // http://mathlog.h11.ru/index.html

  7. Cистемa федеральных образовательных порталов . —

Режим лоступа:

Источник: https://multiurok.ru/files/postroenie-tablits-istinnosti.html

Таблица истинности онлайн с примерами — логика

Таблица истинности — это таблица, которая описывает логическую функцию. Логическая функция здесь — это функция, у которой значения переменных и значение самой функции выражают истинность. Например, они принимают значения «истина» либо «ложь» (true либо false, 1 либо 0).

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

Количество всех существующих комбинаций в таблице находится по формуле N=2*n; где N — общее количество возможных комбинаций, n — число входных переменных.

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

Таблицы истинности для основных функций

Построение таблиц истинности - в помощь студенту

Примеры: конъюнкция — 1&0=0, импликация — 1→0=0.

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

Инверсия; Конъюнкция; Дизъюнкция; Импликация; Эквиваленция; Штрих Шеффера; Стрелка Пирса.

Последовательность построения (составления) таблицы истинности:

https://uchim.org/matematika/tablica-istinnosti — uchim.org

  1. Определить количество N используемых переменных в логическом выражении.
  2. Вычислить количество всевозможных наборов значений переменных M = 2N , равное количеству строк в таблице.
  3. Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество логических операций.
  4. Озаглавить столбцы таблицы названиями переменных и названиями логических операций.
  5. Заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырех переменных.
  6. Заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо.
  7. Заполнить окончательный столбец значений для функции F.

Таким образом, можно составить (построить) таблицу истинности самостоятельно.

Составить таблицу истинности онлайн

Заполните поле ввода и нажмите OK. T — истина, F — ложь. Рекомендуем добавить страницу в закладки или сохранить в социальной сети.

Обозначения

  1. Множества или выражения большими буквами латинского алфавита: A, B, C, D…

  2. A' — штрих — дополнения множеств
  3. && — конъюнкция («и»)
  4. || — дизъюнкция («или»)
  5. ! — отрицание (например, !A)
  6. cap — пересечение множеств cap
  7. cup — объединение множеств (сложение) cup
  8. A&!B — разность множеств A∖B=A-B
  9. A=>B — импликация «Если …, то»
  10. AB — эквивалентность

Всё для учебы » Математика в школе » Таблица истинности онлайн с примерами — логика

Группа с кучей полезной информации (подпишитесь, если предстоит ЕГЭ или ОГЭ):

Источник: https://uchim.org/matematika/tablica-istinnosti

Логические выражения и таблица истинности в примерах решения задач

  • Теория по этой теме по этой теме Пройти тестирование по этой теме Контрольная по этой теме
  •  №1.
  • Докажите, что А В равносильно (A/ ¬B) / (¬A/ B)
  •  Для доказательства равносильности двух высказываний достаточно построить таблицу истинности для высказывания (A/ ) / (/B) и сравнить ее с таблицей истинности эквивалентности:
А В ¬B A/¬B ¬A ¬AVB (A/¬B) / (¬A /B)
1 1 1 1 1
1 1 1
1 1 1
1 1 1 1 1

Последние столбцы этих функций совпадают, значит, они равносильны. ЧТД.

  1. №2.
  2. Укажите, какое логическое выражение равносильно выражению 
  3. A / ¬ (¬B / C)
  4.    1) ¬A / ¬B / ¬C
  5.    2) A / ¬B / ¬C  
  6.    3) A / B / ¬C 
  7.    4) A / ¬B / C
  8. Ответ:  3
  9. №3.
  10. Постройте таблицу истинности для логического выражения:
  11. 1)A=>B ¬А / B 
  12. Ответ:
Читайте также:  Организация индивидуального информационного пространства - в помощь студенту
А В A=>B ¬А A → B ¬А A → B ¬А / B
1 1 1 1
1 1 1
1 1 1
1 1 1 1
  • 2)F=AB(¬А / B) / (¬B/ А)
  • Ответ:
  • №4.
  • Определите истинность следующего высказывания: «За окном светит солнце, и нет дождя».
  • Решение:
  • Нам дано сложное составное высказывание. Выделим из него простые высказывания:
  • А = «За окном светит солнце»
  • В = «За окном дождь»
  •  Составим логическую функцию, соответствующую данному высказыванию.
  • F(A, B) = A / ¬B
  • построим таблицу истинности для данной логической функции.
A B ¬B A / ¬B
1
1
1 1 1
1 1

 Ответ: логическое выражение принимает значение истина только при наборе F(1,0)=1.Следовательно, данное нам высказывание истинно только тогда, когда первое простое высказывание истинно, а второе ложно.

  1. №5.
  2. Определите истинность следующего высказывания: «Гости смеялись, шутили и не расходились по домам».
  3. Решение:
  4. Выделим из данного сложного высказывания простые высказывания:
  5. А = «Гости смеялись»
  6. В = «Гости шутили»
  7. С = «Гости расходились по домам»
  8. Составим логическую функцию, соответствующую данному высказыванию.
  9. F(A, B, С) = A/ B /¬C
  10. Построим таблицу истинности для данной логической функции.
A B C ¬C A / BC
1
1
1 1
1 1
1 1
1 1
1 1 1 1
1 1 1

Ответ: логическое выражение принимает значение истина только при наборе F(1,1,0)=1.Следовательно, данное нам высказывание истинно только тогда, когда первое и второе простые высказывания истинны, а второе ложно.

  • №6.
  • На языке алгебры логики составьте истинное тождество, соответствующее заданному условию задачи:
  • Школьника, Миша, остававшийся в классе на перемене, был вызван к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчик ответили следующее: «Я не бил окно, и Коля тоже…»
  • Известно, что он либо сказал чистую правду, либо в одной части заявления соврал, а другое его высказывание истинно, либо оба факта исказил.
  • Решение:
  • Пусть
  • А = «Окно разбил Миша»
  • В = «Окно разбил Коля»
  • Если Миша сказал чистую правду, то¬А / ¬В = 1.
  • Если в одной части заявления Миша соврал, а другое его высказывание истинно, то (¬А / В) / (А /¬В) = 1
  • Если Миша оба факта исказил, то А / В = 1.
  • Ответ:
  • Истинное тождество, соответствующее условию задачи будет выглядеть так: ¬А / ¬В  /¬А / В /А / ¬ В / А / В = 1.

Источник: https://mir-logiki.ru/virag_tabl_prim/

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

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

Простая конъюнкция

  • полная, если в неё каждая переменная { или её отрицание } входит ровно 1 раз;
  • монотонная, если она не содержит отрицаний переменных.

ДНФ { Дизъюнктивная Нормальная Форма } — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов.

Пример ДНФ: $f(x,y,z) = (x land y) lor (y land
eg { z } )$

СДНФ

СДНФ { Совершенная Дизъюнктивная Нормальная Форма } — это такая ДНФ, которая удовлетворяет условиям:

  • в ней нет одинаковых простых конъюнкций
  • каждая простая конъюнкция полная
  • Пример СДНФ: $f(x,y,z) = (x land
    eg { y } land z) lor (x land y land
    eg { z } )$
  • Теорема: Для любой булевой функции $f(vec { x } )$, не равной тождественному нулю (), существует СДНФ, ее задающая.
  • Доказательство:
  • Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.
  • $f(vec { x } ) =
    eg x_i wedge f(x_1, dots ,x_ { i-1 } ,0,x_ { i+1 } , dots ,x_n) vee x_i wedge f(x_1, dots ,x_ { i-1 } ,1,x_ { i+1 } , dots ,x_n)$

Данное соотношение легко проверить подстановкой всевозможных значений $x_i$ { $0$ и $1$ } . Эта формула позволяет выносить $x_i$ за знак функции. Последовательно вынося $x_1$, $x_2$,.., $x_n$ за знак $f(vec { x } )$, получаем следующую формулу :

$ f(vec { x } ) =
eg x_1 wedge
eg x_2 wedge …wedge
eg x_ { n-1 } wedge
eg x_n wedge f(0,0,…,0,0)~vee~$

$
eg x_1 wedge
eg x_2 wedge … wedge
eg x_ { n-1 } wedge x_n wedge f(0,0,…,0,1) ~vee~ $ $dots $ $~vee~ x_1 wedge x_2 wedge … wedge x_ { n-1 } wedge
eg x_n wedge f(1,1,…,1,0) ~vee~ $ $x_1 wedge x_2 wedge … wedge x_ { n-1 } wedge x_n wedge f(1,1,…,1) $

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от $n$ переменных мы имеем { { { $2^ { n } $ } } } конъюнктов.

Каждый из них соответствует значению функции на одном из { { { $2^ { n } $ } } } возможных наборов значений $n$ переменных. Если на некотором наборе $f(vec { x } )=0$, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить.

Если же $ f(vec { x } )=1$, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

Алгоритм построения СДНФ по таблице истинности

  • В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
  • Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
  • Все полученные конъюнкции связываем операциями дизъюнкции.
Читайте также:  Теория конкурентных преимуществ - в помощь студенту

Пример построения СДНФ для медианы

  1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.

    x y z $langle x,y,z
    angle$
    0 0 0 0
    0 0 1 0
    0 1 1 0
    0 1 1 1
    1 0 0 0
    1 0 1 1
    1 1 0 1
    1 1 1 1
  2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

    x y z $ langle x,y,z
    angle $
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 1 1 1 $(
    eg { x } land y land z)$
    1 0 0 0
    1 0 1 1 $(x land
    eg { y } land z)$
    1 1 0 1 $(x land y land
    eg { z } )$
    1 1 1 1 $(x land y land z)$
  3. Все полученные конъюнкции связываем операциями дизъюнкции. $ langle x,y,z
    angle = (x land y land z) lor (
    eg { x } land y land z) lor (x land
    eg { y } land z) lor (x land y land
    eg { z } )$

Примеры СДНФ для некоторых функций

  1. Стрелка Пирса: $x downarrow y = (
    eg { x } land
    eg { y } )$
  2. Исключающее или: $x oplus y oplus z = (overline { x } land overline { y } land z) lor (overline { x } land y land overline { z } ) lor (x land overline { y } land overline { z } ) lor (x land y land z)$
  3. Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:
  4. а } в ней нет одинаковых дизъюнктивных элементов;
  5. б } ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;
  6. в } ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;
  7. г } в каждой элементарной конъюнкции содержится либо $X_i$, либо $overline { X } _i$, где $i = 1, n$.
  8. Условие а } – г } являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:
  9. 1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $Bwedge (X_ivee overline { X } _i) equiv (Bwedge X_i)vee (Bwedge overline { X } _i)$;
  10. 2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;
  11. 3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;
  12. 4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Формула называется дизъюнктивной нормальной формой { ДНФ } , если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1vee A_2vee …vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.

Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой { СДНФ } , если:

  1. $A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;

  2. Все элементарные конъюнкции в такой ДНФ попарно различны.

  • Например: $A = x_1 wedge$ НЕ $x_2 vee x_1 wedge x_2$
  • Совершенная дизъюнктивная нормальная форма представляет собой формулу, построенную по строго определенным правилам с точностью до порядка следования элементарных конъюнкций { дизъюнктивных членов } в ней.
  • Она является примером однозначного представления булевой функции в виде формульной { алгебраической } записи.

Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.

Алгоритм построения СДНФ по таблице истинности:

  • В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
  • Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
  • Все полученные конъюнкции связываем операциями дизъюнкции.

Далее:

Поверхностный интеграл второго рода и его свойства

Механические и физические приложения поверхностного интеграла первого рода

Вычисление поверхностного интеграла первого рода

Поверхностный интеграл первого рода и его свойства

Вычисление поверхностного интеграла второго рода

Механические приложения тройного интеграла

Векторное поле

Нормальные формы

Теорема Стокса

Формула Гаусса — Остроградского

Переход от двойного интеграла к повторному. Изменение порядка интегрирования. Переход к полярным координатам

Вычисление криволинейного интеграла первого рода. Примеры

Определение двойного интеграла

Определение тройного интеграла. Теорема существования тройного интеграла

Огравление $Rightarrow $

Источник: https://3dstroyproekt.ru/algebra-logici/sdnf

Ссылка на основную публикацию