\"bottom\""},"equivalents":{"wt":"''P'' ∧ ¬''P''
O''pq''"},"truthtable00":{"wt":"0"},"truthtable01":{"wt":"0"},"truthtable10":{"wt":"0"},"truthtable11":{"wt":"0"},"image":{"wt":"Venn0000.svg"}},"i":0}}]}" id="mwRA">
Notation  Equivalent formulas  Truth table  Venn diagram  
"bottom"  P∧ ¬P Opq 

Notation  Equivalent formulas  Truth table  Venn diagram  
"top"  P∨ ¬P Vpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P  p Ipq 

Notation  Equivalent formulas  Truth table  Venn diagram  
¬P ~P  Np Fpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
Q  q Hpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
¬Q ~Q  Nq Gpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P∧Q P & Q P · Q P AND Q  P ↛¬Q ¬P ↚ Q ¬P ↓ ¬Q Kpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P ↑ Q PQ P NAND Q  P → ¬Q ¬P ← Q ¬P∨ ¬Q Dpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P∨Q P OR Q  P ← ¬Q ¬P → Q ¬P ↑ ¬Q ¬(¬P∧ ¬Q) Apq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P ↓ Q P NOR Q  P ↚ ¬Q ¬P ↛ Q ¬P∧ ¬Q Xpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P ↛ Q PQ PQ  P∧ ¬Q ¬P ↓ Q ¬P ↚ ¬Q Lpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P → Q P⊃Q PQ  P ↑ ¬Q ¬P∨Q ¬P ← ¬Q Cpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P ↚ Q PQ PQ  P ↓ ¬Q ¬P∧Q ¬P ↛ ¬Q Mpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P ← Q P⊂Q PQ  P∨ ¬Q ¬P ↑ Q ¬P → ¬Q Bpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
P ↮ Q P ≢ Q P ⨁ Q P XOR Q  P ¬Q ¬PQ ¬P ↮ ¬Q Jpq 

Notation  Equivalent formulas  Truth table  Venn diagram  
PQ P ≡ Q P XNOR Q P IFF Q  P ↮ ¬Q ¬P ↮ Q ¬P ¬Q Epq 

Because a function may be expressed as a composition, a truthfunctional logical calculus does not need to have dedicated symbols for all of the abovementioned functions to be functionally complete. This is expressed in a propositional calculus as logical equivalence of certain compound statements. For example, classical logic has ¬P ∨ Q equivalent to P → Q. The conditional operator "→" is therefore not necessary for a classicalbased logical system if "¬" (not) and "∨" (or) are already in use.
A minimal set of operators that can express every statement expressible in the propositional calculus is called a minimal functionally complete set. A minimally complete set of operators is achieved by NAND alone {↑} and NOR alone {↓}.
The following are the minimal functionally complete sets of operators whose arities do not exceed 2:^{ [5] }
Some truth functions possess properties which may be expressed in the theorems containing the corresponding connective. Some of those properties that a binary truth function (or a corresponding logical connective) may have are:
A set of truth functions is functionally complete if and only if for each of the following five properties it contains at least one member lacking it:
A concrete function may be also referred to as an operator. In twovalued logic there are 2 nullary operators (constants), 4 unary operators, 16 binary operators, 256 ternary operators, and nary operators. In threevalued logic there are 3 nullary operators (constants), 27 unary operators, 19683 binary operators, 7625597484987 ternary operators, and nary operators. In kvalued logic, there are k nullary operators, unary operators, binary operators, ternary operators, and nary operators. An nary operator in kvalued logic is a function from . Therefore, the number of such operators is , which is how the above numbers were derived.
However, some of the operators of a particular arity are actually degenerate forms that perform a lowerarity operation on some of the inputs and ignores the rest of the inputs. Out of the 256 ternary boolean operators cited above, of them are such degenerate forms of binary or lowerarity operators, using the inclusion–exclusion principle. The ternary operator is one such operator which is actually a unary operator applied to one input, and ignoring the other two inputs.
"Not" is a unary operator, it takes a single term (¬P). The rest are binary operators, taking two terms to make a compound statement (P∧Q, P∨Q, P → Q, P ↔ Q).
The set of logical operators Ω may be partitioned into disjoint subsets as follows:
In this partition, is the set of operator symbols of arity j.
In the more familiar propositional calculi, is typically partitioned as follows:
Instead of using truth tables, logical connective symbols can be interpreted by means of an interpretation function and a functionally complete set of truthfunctions (Gamut 1991), as detailed by the principle of compositionality of meaning. Let I be an interpretation function, let Φ, Ψ be any two sentences and let the truth function f_{nand} be defined as:
Then, for convenience, f_{not}, f_{or}f_{and} and so on are defined by means of f_{nand}:
or, alternatively f_{not}, f_{or}f_{and} and so on are defined directly:
Then
etc.
Thus if S is a sentence that is a string of symbols consisting of logical symbols v_{1}...v_{n} representing logical connectives, and nonlogical symbols c_{1}...c_{n}, then if and only if I(v_{1})...I(v_{n}) have been provided interpreting v_{1} to v_{n} by means of f_{nand} (or any other set of functional complete truthfunctions) then the truthvalue of is determined entirely by the truthvalues of c_{1}...c_{n}, i.e. of I(c_{1})...I(c_{n}). In other words, as expected and required, S is true or false only under an interpretation of all its nonlogical symbols.
Logical operators are implemented as logic gates in digital circuits. Practically all digital circuits (the major exception is DRAM) are built up from NAND, NOR, NOT, and transmission gates. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.
The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.
The fact that all truth functions can be expressed with NOR alone is demonstrated by the Apollo guidance computer.
In logic, disjunction is a logical connective typically notated whose meaning either refines or corresponds to that of natural language expressions such as "or". In classical logic, it is given a truth functional semantics on which is true unless both and are false. Because this semantics allows a disjunctive formula to be true when both of its disjuncts are true, it is an inclusive interpretation of disjunction, in contrast with exclusive disjunction. Classical proof theoretical treatments are often given in terms of rules such as disjunction introduction and disjunction elimination. Disjunction has also been given numerous nonclassical treatments, motivated by problems including Aristotle's sea battle argument, Heisenberg's uncertainty principle, as well the numerous mismatches between classical disjunction and its nearest equivalents in natural language.
Firstorder logic—also known as predicate logic, quantificational logic, and firstorder predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. Firstorder logic uses quantified variables over nonlogical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of firstorder logic.
In logic, mathematics and linguistics, And is the truthfunctional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true. The logical connective that represents this operator is typically written as or ⋅ .
In logic, a logical connective is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zerothorder logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ.
In logic, negation, also called the logical complement, is an operation that takes a proposition to another proposition "not ", written , or . It is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .
Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.
In boolean logic, logical nor or joint denial is a truthfunctional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false. It is logically equivalent to and , where the symbol signifies logical negation, signifies OR, and signifies AND. In grammar, nor is a coordinating conjunction.
In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective used to conjoin two statements P and Q to form the statement "P if and only if Q", where P is known as the antecedent, and Q the consequent. This is often abbreviated as "P iff Q". Other ways of denoting this operator may be seen occasionally, as a doubleheaded arrow, a prefixed E "Epq", an equality sign (=), an equivalence sign (≡), or EQV. It is logically equivalent to both and , and the XNOR boolean operator, which means "both or neither".
Computation tree logic (CTL) is a branchingtime logic, meaning that its model of time is a treelike structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realized. It is used in formal verification of software or hardware artifacts, typically by software applications known as model checkers, which determine if a given artifact possesses safety or liveness properties. For example, CTL can specify that when some initial condition is satisfied, then all possible executions of a program avoid some undesirable condition. In this example, the safety property could be verified by a model checker that explores all possible transitions out of program states satisfying the initial condition and ensures that all such executions satisfy the property. Computation tree logic belongs to a class of temporal logics that includes linear temporal logic (LTL). Although there are properties expressible only in CTL and properties expressible only in LTL, all properties expressible in either logic can also be expressed in CTL*.
Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus. It gives the functional value true if both functional arguments have the same logical value, and false if they are different.
In mathematical logic, a tautology is a formula or assertion that is true in every possible interpretation. An example is "x=y or x≠y". Similarly, "either the ball is green, or the ball is not green" is always true, regardless of the colour of the ball.
In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A wellknown complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. Each of the singleton sets { NAND } and { NOR } is functionally complete.
In logic, conditioned disjunction is a ternary logical connective introduced by Church. Given operands p, q, and r, which represent truthvalued propositions, the meaning of the conditioned disjunction [p, q, r] is given by:
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statement has its antecedent and consequent inverted and flipped.
Tnorm fuzzy logics are a family of nonclassical logics, informally delimited by having a semantics that takes the real unit interval [0, 1] for the system of truth values and functions called tnorms for permissible interpretations of conjunction. They are mainly used in applied fuzzy logic and fuzzy set theory as a theoretical basis for approximate reasoning.
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation. The general study of interpretations of formal languages is called formal semantics.
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.