Основные понятия и законы математической логики



Скачать 62.11 Kb.
Дата19.01.2013
Размер62.11 Kb.
ТипДокументы

Справочный материал

Тема: Основные понятия и законы математической логики.
Справочный материал

  • Условные обозначения логических операций:

¬ A, не A (отрицание, инверсия);

A B, А*В, A и B (логическое умножение, конъюнкция);

A B, А+В, A или B (логическое сложение, дизъюнкция);

AB импликация (следование).


  • Таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация»:

И

ИЛИ

НЕ

ИМПЛИКАЦИЯ

0*0=0

0+0=0

0=не 1

0 → 0 = 1

0*1=0

0+1=0

1= не 0

1 → 0 = 0

1*0=0

1+0=0




1 → 1 = 1

1*1=1

1+1=1




0 → 1 = 1




  • Операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

AB = ¬ A B или в других обозначениях AB = ;

  • Если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»;






  • Формулы де Моргана:

¬ (A  B) = ¬ A  ¬ B

¬ (A  B) = ¬ A  ¬ B gif" name="object4" align=absmiddle width=85 height=18>

Пример 1


Для какого из указанных значений X истинно высказывание ¬((X > 2)→(X > 3))?

1) 1 2) 2 3) 3 4) 4

Решение (прямая подстановка):

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

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

  3. По таблице истинности операции «импликация» находим третий столбец (значение выражения в больших скобках), применив операцию «импликация» к значениям второго и третьего столбцов (в каждой строке).

  4. Значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):

    X

    X > 2

    X > 3

    (X > 2)→(X > 3)

    ¬((X > 2)→(X > 3))

    1

    0

    0

    1

    0

    2

    0

    0

    1

    0

    3

    1

    0

    0

    1

    4

    1

    1

    1

    0

  5. Таким образом, ответ – 3.


Пример 2


Каково наибольшее целое число X, при котором истинно высказывание

(50 < X·X) (50 > (X+1)·(X+1))

Решение 1

  1. Это операция импликации между двумя отношениями и ;

  2. Попробуем сначала решить неравенства

,

  1. Можно преобразовать импликацию, выразив ее через «ИЛИ» и «НЕ»:



  1. Вспомним таблицу истинности операции «импликация»:

    A

    B

    A → B

    0

    0

    1

    0

    1

    1

    1

    0

    0

    1

    1

    1

  2. Согласно таблице, заданное выражение истинно везде, кроме областей, где и ;

  3. Поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7;

  4. Таким образом, верный ответ – 7 .

Пример 3


Сколько различных решений имеет уравнение

((K L) (L M N)) = 0

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Решение (вариант 1):

  1. Перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

  1. Из таблицы истинности операции «импликация» следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1 и L · M · N = 0

  1. Из первого уравнения следует, что хотя бы одна из переменных, K или L равна 1 (или обе вместе); поэтому рассмотрим три случая;

  2. Если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения;

  3. Если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения;

  4. Если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения;

  5. Таким образом, всего получаем 4 + 3 + 3 = 10 решений.

Пример 4


Укажите значения переменных К, L, M, N, при которых логическое выражение

(¬(М L) К) (¬К ¬М) N)

ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

Решение

  1. Запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):



  1. Из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных;

  2. Из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно

и

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

  2. Из второго условия, , при и получаем ;

  3. Таким образом, правильный ответ – 1000.

Похожие:

Основные понятия и законы математической логики iconЭлементы математической логики
Простейшую из формальных логических теорий называют алгеброй высказываний, поэтому начнем знакомство с элементами математической...
Основные понятия и законы математической логики iconЗаконы (принципы) формальной логики Логическая культура. Значение логики. Язык логики. Семантические категории языка
Отношения между понятиями (сравнимые и несравнимые, совместимые и несовместимые понятия)
Основные понятия и законы математической логики iconОсновные понятия математической логики
«большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках
Основные понятия и законы математической логики iconЛогинов А. С. Часть Дифференциальное исчисление
В разделе рассматриваются основные понятия теории множеств, определение множества действительных чисел. Приводится необходимая терминология...
Основные понятия и законы математической логики icon«История создания математической логики»
В связи с этим математика являлась основным потребителем логики. Очевидно, поэтому развитие математики выявило недостаточность Аристотелевой...
Основные понятия и законы математической логики iconОсновные понятия математической логики
Рассуждение- это цепочка взаимосвязанных суждений, фактов, общих положений и умозаключений, получаемых из других суждений по определенным...
Основные понятия и законы математической логики iconЭлементы математической логики. Законы логики. Упрощение логических формул
Существуют такие наборы логических функций, с помощью которых можно выразить любые другие логические функции. Они называются функционально...
Основные понятия и законы математической логики iconЛекция №5. Условный оператор, оператор выбора. Логические операции в Паскале, таблица истинности, основные законы алгебры логики
Операции отношений. Логические операторы в Паскале. Таблицы истинности. Основные законы алгебры логики
Основные понятия и законы математической логики iconЗаконы алгебры логики 2 Закон одинарных элементов 2 Законы отрицания 3 Комбинационные законы 4 Правило поглощения 5
Этот закон непосредственно следует из приведённых выше выражений аксиом алгебры логики
Основные понятия и законы математической логики iconА. В. Титов Диалектические аспекты развития современной математики и математической логики. «Все, что нас окружает, может рассматриваться как пример диалектики.»
Математика относится к циклу формальных наук, в которых не действуют принципы спекулятивной философии Г. В. Ф. Гегеля. Основу логики...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org