Днф это: ДНФ | это… Что такое ДНФ?

alexxlab / / Разное

Дизъюнктивная нормальная форма | это… Что такое Дизъюнктивная нормальная форма?

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Содержание

  • 1 Примеры и контрпримеры
  • 2 Построение ДНФ
    • 2.1 Алгоритм построения ДНФ
    • 2.2 Пример построения ДНФ
  • 3 k-дизъюнктивная нормальная форма
  • 4 Переход от ДНФ к СДНФ
  • 5 Формальная грамматика, описывающая ДНФ
  • 6 См. также
  • 7 Примечания
  • 8 Литература
  • 9 Ссылки

Формулы в ДНФ:

Формулы не в ДНФ:

Построение ДНФ

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

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

Это можно сделать, используя равносильные формулы:

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

3) Избавиться от знаков двойного отрицания.

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

Пример построения ДНФ

Приведем к ДНФ формулу :

Выразим логические операции → и ↓ через :

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

Используя закон дистрибутивности, приводим формулу к ДНФ:

k-дизъюнктивная нормальная форма

k-дизъюнктивная нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно

k литералов.

Например, следующая формула записана в 2-ДНФ:

Переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение :, после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как по закону Идемпотентности). Например:

Таким образом, из ДНФ получили СДНФ.

Формальная грамматика, описывающая ДНФ

Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:

<ДНФ> → <конъюнкт>
<ДНФ> → <ДНФ> ∨ <конъюнкт>
<конъюнкт> → <литерал>
<конъюнкт> → (<конъюнкт> ∧ <литерал>)
<литерал> → <терм>
<литерал> → ¬<терм>

где <терм> обозначает произвольную булеву переменную.

См. также

  • Конъюнктивная нормальная форма
  • Дистрибутивность
  • Нормальная форма (математика)
  • Закон двойного отрицания
  • Законы де Моргана

Примечания

  1. ↑ Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.

Литература

  • Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике — 2-е изд., испр. — М.: Айрис-пресс, 2008. — 176 с. — (Высшее образование)

Ссылки

  • ДНФ, СДНФ, КНФ, СКНФ
  • Disjunctive Normal Form
  • Дизъюнктивная и Конъюнктивная нормальные формы

Команда dnf | Linux FAQ

Команда dnf предназначена для работы с одноименной утилитой, которая используется для управлении пакетами программного обеспечения в дистрибутивах RHEL, CentOS, а также Fedora Workstation (в первых двух дистрибутивах она пока не используется по умолчанию). Данная утилита пришла на смену широко известной утилите

yum из-за проблем с производительностью и потреблением памяти последней. На сегодняшний день утилита dnf обладает всеми возможностями утилиты yum и является ее полноценной заменой, менее требовательной к ресурсам системы.

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

Базовый синтаксис команды выглядит следующим образом:

# dnf [параметры] [команда] имена-пакетов-или-групп

Утилита поддерживает большое количество команд и параметров. Чаще всего используются такие параметры, как параметр —skip-broken

, позволяющий пропускать пакеты с проблемами зависимостей, параметр —allowerasing, позволяющий удалять пакеты для разрешения зависимостей, параметр —cacheonly (или -C), позволяющий использовать кэшированные метаданные без их обновления, параметры —assumeyes (или -y) и —assumeno, позволяющие автоматически отвечать утвердительно или отрицательно на все вопросы утилиты, параметры —enablerepo и —disablerepo, позволяющие активировать и деактивировать указанный репозиторий, а также параметр —exclude (или -x), позволяющий исключить из рассмотрения пакет с указанным именем. Основными командами являются:

Команда Назначение
install Установка пакета с заданным именем
reinstall Переустановка пакета с заданным именем

update

upgrade

 Обновление пакета с заданным именем

remove

erase

 Удаление пакета с заданным именем
autoremove Удаление осиротевших пакетов
info Получение информации о пакете с заданным именем
provides Получение имени пакета, в котором имеется файл с заданным именем
search Поиск пакетов с заданным словом в имени
list Вывод имен всех доступных и установленных пакетов
list installed
 Вывод списка всех установленных пакетов
list available Вывод списка всех доступных пакетов
repolist Вывод списка подключенных репозиториев
repolist all Вывод списка всех репозиториев
clean all Удаление всех метаданных
history Вывод истории использования dnf
groupunstall Установка всех пакетов из группы с заданным именем
groupupdate Обновление всех пакетов из группы с заданным именем
groupremove Удаление всех пакетов из группы с заданным именем
grouplist Вывод имен всех существующих групп пакетов

Автоматическая загрузка обновлений

В дистрибутиве Fedora Workstation dnf используется также для автоматической загрузки обновлений системы. Если вам не нужна эта функция (например, вы привыкли устанавливать обновления вручную или используете сетевое соединение с ограничением по трафику), вы можете деактивировать ее следующим образом.

В первую очередь следует деактивировать соответствующие службу и таймер systemd:

# systemctl disable dnf-makecache.service
# systemctl disable dnf-makecache.timer

Далее нужно отключить механизм автоматической загрузки обновлений на уровне службы packagekitd:

$ gsettings set org.gnome.software download-updates false

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

Примеры использования

Установка пакета программного обеспечения

Для установки пакета программного обеспечения достаточно просто использовать команду install:

# dnf install midori
Последняя проверка окончания срока действия метаданных: 1:17:29 назад, Пн 31 июл 2017 17:36:45. 
Зависимости разрешены.
================================================================================
 Пакет           Архитектура     Версия                   Репозиторий     Размер
================================================================================
Установка:
 midori          x86_64          0.5.12-0.2.fc26          fedora          1.3 M
Результат транзакции
================================================================================
Установка  1 Пакет
Объем загрузки: 1.3 M
Объем изменений: 6.2 M
Продолжить? [д/Н]: y
Загрузка пакетов:
midori-0.5.12-0.2.fc26.x86_64.rpm               621 kB/s | 1.3 MB     00:02    
--------------------------------------------------------------------------------
Общий размер                                    277 kB/s | 1.3 MB     00:04     
Проверка транзакции
Проверка транзакции успешно завершена.
Идет проверка транзакции
Тест транзакции проведен успешно
Выполнение транзакции
  Подготовка      :                                                         1/1 
  Установка       : midori-0.
 
 5.12-0.2.fc26.x86_64                           1/1 
  Запуск скриплета: midori-0.5.12-0.2.fc26.x86_64                           1/1 
  Проверка        : midori-0.5.12-0.2.fc26.x86_64                           1/1 
Установлено:
  midori.x86_64 0.5.12-0.2.fc26                                                 
Выполнено!
Удаление пакета программного обеспечения

Удаление пакета программного обеспечения осуществляется с помощью команды remove:

# dnf remove midori
Зависимости разрешены.
================================================================================
 Пакет          Архитектура    Версия                     Репозиторий     Размер
================================================================================
Удаление:
 midori         x86_64         0.5.12-0.2.fc26            @fedora         6.2 M
Результат транзакции
================================================================================
Удаление  1 Пакет
Освобожденное место: 6. 2 M
Продолжить? [д/Н]: y
Проверка транзакции
Проверка транзакции успешно завершена.
Идет проверка транзакции
Тест транзакции проведен успешно
Выполнение транзакции
  Подготовка      :                                                         1/1 
  Удаление        : midori-0.5.12-0.2.fc26.x86_64                           1/1 
  Запуск скриплета: midori-0.5.12-0.2.fc26.x86_64                           1/1 
  Проверка        : midori-0.5.12-0.2.fc26.x86_64                           1/1 
Удален:
  midori.x86_64 0.5.12-0.2.fc26                                                 
Выполнено!
Поиск пакета программного обеспечения

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

# dnf -C search midori
Последняя проверка окончания срока действия метаданных: 1:09:54 назад, Пн 31 июл 2017 17:36:45.
========================= Имя Exactly Matched: midori ==========================
midori. x86_64 : A lightweight GTK+ web browser
midori.i686 : A lightweight GTK+ web browser
Обновление пакетов программного обеспечения

Для установки всех обновлений системы достаточно использовать команду update:

# dnf update
Последняя проверка окончания срока действия метаданных: 1:24:50 назад, Пн 31 июл 2017 17:36:45.
Зависимости разрешены.
Отсутствуют действия для выполнения
Выполнено!
Определение

в кембриджском словаре английского языка

Переводы DNF

на Китайский (традиционный) 、自行車選手或賽車手等）中途退賽的（не закончил 的縮寫）…

на Китайский (упрощенный)

车选手或赛车手等）中途退赛的（делал не закончить 的缩写）…

Узнать больше

Нужен переводчик?

Получите быстрый бесплатный перевод!

Как произносится DNF ?