Propositional calculus | Normal forms (logic)

Negation normal form

In mathematical logic, a formula is in negation normal form (NNF) if the negation operator is only applied to variables and the only other allowed Boolean operators are conjunction and disjunction . Negation normal form is not a canonical form: for example, and are equivalent, and are both in negation normal form. In classical logic and many modal logics, every formula can be brought into this form by replacing implications and equivalences by their definitions, using De Morgan's laws to push negation inwards, and eliminating double negations. This process can be represented using the following rewrite rules (Handbook of Automated Reasoning 1, p. 204): [In these rules, the symbol indicates logical implication in the formula being rewritten, and is the rewriting operation.] Transformation into negation normal form can increase the size of a formula only linearly: the number of occurrences of atomic formulas remains the same, the total number of occurrences of and is unchanged, and the number of occurrences of may double. A formula in negation normal form can be put into the stronger conjunctive normal form or disjunctive normal form by applying distributivity. Repeated application of distributivity may exponentially increase the size of a formula. In the classical propositional logic, transformation to negation normal form does not impact computational properties: the satisfiability problem continues to be NP-complete, and the validity problem continues to be co-NP-complete. For formulas in CNF, validity problem is solvable in polynomial time, and for formulas in DNF, the satisfiability problem is solvable in polynomial time. (Wikipedia).

Video thumbnail

Simplify a rational expression

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

Simplify a rational expression

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

How to simplify a rational expression by factoring twice

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

How do we simplify rational expressions

Learn about simplifying rational expressions. A rational expression is an expression in the form of a fraction. To simplify a rational expression is to put the expression in a simplified form i.e. cancel out common factors, etc. When given a rational function such that the numerator and

From playlist Simplify Rational Expressions

Video thumbnail

Simplify a rational expression

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

Complete Simplifying Rational Expressions

Learn about simplifying rational expressions. A rational expression is an expression in the form of a fraction. To simplify a rational expression is to put the expression in a simplified form i.e. cancel out common factors, etc. When given a rational function such that the numerator and

From playlist Learn about Simplifying Rational Expressions #Rational

Video thumbnail

What do I need to know to simplify rational expressions

Learn about simplifying rational expressions. A rational expression is an expression in the form of a fraction. To simplify a rational expression is to put the expression in a simplified form i.e. cancel out common factors, etc. When given a rational function such that the numerator and

From playlist Simplify Rational Expressions

Video thumbnail

Simplifying a rational expression by factoring

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

Simplify a rational expression by factoring

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

Logic 6 - Propositional Resolutions | Stanford CS221: AI (Autumn 2021)

For more information about Stanford's Artificial Intelligence professional and graduate programs visit: https://stanford.io/ai Associate Professor Percy Liang Associate Professor of Computer Science and Statistics (courtesy) https://profiles.stanford.edu/percy-liang Assistant Professor

From playlist Stanford CS221: Artificial Intelligence: Principles and Techniques | Autumn 2021

Video thumbnail

Year 13/A2 Pure Chapter 0.2 (Subsets of Real Numbers, Representatives and Proof)

This video is the second of two preparatory lessons that introduce the second year A-Level (A2) content. The aim of this lesson is to provide a firm foundation of the underlying logic, principles and strategies required to fully understand the concept of mathematical proof. In particular,

From playlist Year 13/A2 Pure Mathematics

Video thumbnail

Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF) - Logic

In this video on #Logic, we learn how to find the Sum of Products (SOP) and Product of Sums (POS). This is also known as Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF). We focus on the procedure and I briefly explain why it works. 0:00 - [Intro] 1:36 - [Sum of Products /

From playlist Logic in Philosophy and Mathematics

Video thumbnail

Logic 9 - First Order Resolution | Stanford CS221: AI (Autumn 2021)

For more information about Stanford's Artificial Intelligence professional and graduate programs visit: https://stanford.io/ai Associate Professor Percy Liang Associate Professor of Computer Science and Statistics (courtesy) https://profiles.stanford.edu/percy-liang Assistant Professor

From playlist Stanford CS221: Artificial Intelligence: Principles and Techniques | Autumn 2021

Video thumbnail

Binary 8 – Floating Point Binary Subtraction

This is the eighth in a series of videos about the binary number system which is fundamental to the operation of a digital electronic computer. In particular, this video covers subtraction of floating point binary numbers for a given sized mantissa and exponent, both in two’s complement.

From playlist Binary

Video thumbnail

General Practical Tips | Stanford CS224U Natural Language Understanding | Spring 2021

For more information about Stanford's Artificial Intelligence professional and graduate programs visit: https://stanford.io/ai To learn more about this course visit: https://online.stanford.edu/courses/cs224u-natural-language-understanding To follow along with the course schedule and sy

From playlist Stanford CS224U: Natural Language Understanding | Spring 2021

Video thumbnail

Simplify a rational expression

Learn how to simplify rational expressions. A rational expression is an expression in the form of a fraction where the numerator and/or the denominator are/is an algebraic expression. To simplify a rational expression, we factor completely the numerator and the denominator of the rational

From playlist Simplify Rational Expressions

Video thumbnail

Will Troiani - Introduction to proof nets (Part 1)

In the first of several talks on linear logic and proof nets, building towards the proof of the sequentialisation theorem, Will introduces the sequent calculus of multiplicative linear logic, proof structures and the translation between them. Lecture notes - https://cglseminar.github.io/n

From playlist Computation, Geometry, Logic seminar

Related pages

Disjunctive normal form | Conjunctive normal form | Distributive property | Mathematical logic | Modal logic | Negation | De Morgan's laws | Boolean algebra | Boolean satisfiability problem | Logical conjunction | Handbook of Automated Reasoning | Logical disjunction