Friday, February 06, 2015

Symbolic Logic

In mathematics, a proof is a deductive argument for a mathematical statement. In the argument, other previously established statements, such as theorems, can be used. In principle, a proof can be traced back to self-evident or assumed statements, known as axioms  Mathematical proof

Direct proof
Proof by mathematical induction-
Proof by [S]contraposition[/S]/transposition (P → Q) \Leftrightarrow (¬ Q → ¬ P)
Proof by construction
Proof by exhaustion
Probabilistic proof
Combinatorial proof
Nonconstructive proof
Statistical proofs in pure mathematics

----------------------------------------------------

Modus Ponens-
p → q
p
_____
q

Modus Tollens-
p → q
~q
_____
~p

Hypothetical Syllogism-
p → q
q → r
_____
p → r

Disjunctive Syllogism-
p ∨ q
~ p
_____
q

Constructive Dilemma-
(p → q) • (r → s)
p ∨ r
______
Q ∨ S

Destructive Dilemma-
(p → q) • (r → s)
~q ∨ ~S
______
~P v ~R

Conjunction    -
p
q
_____
p • q

Simplification-
p • q
____
p

p
_____
p ∨ q

----------------------------------------------------------------------

¬     negation (NOT)                     The tilde ( ˜ ) is also often used.
∧     conjunction (AND)             The ampersand ( & ) or dot ( · ) are also often used.
∨     disjunction (OR)                     This is the inclusive disjunction, equivalent to and/or in                                              English.
⊕     exclusive disjunction (XOR)     ⊕ means that only one of the connected propositions
is true, equivalent to either…or. Sometimes ⊻ is used.
|     alternative denial (NAND)     Means “not both”. Sometimes written as ↑
↓     joint denial (NOR)             Means “neither/nor”.
→     conditional (if/then)             Many logicians use the symbol ⊃ instead. This is also
known as material implication.
↔     biconditional (iff)                     Means “if and only if” ≡ is sometimes used, but this site
reserves that symbol for equivalence.

Quantifiers

∀     universal quantifier             Means “for all”, so ∀xPx means that Px is true for every x.
∃     existential quantifier             Means “there exists”, so ∃xPx means that Px is true for at
least one x.
Relations

⊨     implication                             α ⊨ β means that β follows from α
≡     equivalence                     Also ⇔. Equivalence is two-way implication, so α ≡ β
means α implies β and β implies α.
⊢     provability                             Shows provable inference. α is provable β means that
from α we can prove that β.
∴     therefore                             Used to signify the conclusion of an argument. Usually
taken to mean implication, but often used to present
arguments in which the premises do not deductively imply
the conclusion.
⊩     forces                            A relationship between possible worlds and sentences in
modal logic.
Truth-Values

⊤     tautology                            May be used to replace any tautologous (always true)
formula.
formula. Sometimes “F” is used.

Parentheses

( )     parentheses                   Used to group expressions to show precedence of
operations.
Square brackets

[ ]                                          are sometimes used to clarify groupings.
Set Theory

∈     membership                   Denotes membership in a set. If a ∈ Γ, then a is a member
(or an element) of set Γ.
∪     union                          Used to join sets. If S and T are sets of formula, S ∪ T is a
set containing all members of both.
∩     intersection                  The overlap between sets. If S and T are sets of formula, S
∩ T is a set containing those elemenets that are members
of both.
⊆     subset                          A subset is a set containing some or all elements of another
set.
⊂     proper subset                  A proper subset contains some, but not all, elements of
another set.
=     set equality                  Two sets are equal if they contain exactly the same
elements.
∁     absolute complement          ∁(S) is the set of all things that are not in the set S.
Sometimes written as C(S), S or SC.
-     relative complement          T - S is the set of all elements in T that are not also in S.
Sometimes written as T \ S.
∅     empty set                          The set containing no elements.

Modalities

□     necessarily                     Used only in modal logic systems. Sometimes expressed as []
where the symbol is unavailable.
◊     possibly                         Used only in modal logic systems. Sometimes expressed as
<> where the symbol is unavailable.

Propositions, Variables and Non-Logical Symbols

The use of variables in logic varies depending on the system and the author of the logic being presented. However, some common uses have emerged. For the sake of clarity, this site will use the system defined below.

Symbol             Meaning                     Notes

A, B, C … Z     propositions     Uppercase Roman letters signify individual propositions. For example, P may symbolize the proposition “Pat is ridiculous”. P and Q are traditionally used in most examples.

α, β, γ … ω     formulae     Lowercase Greek letters signify formulae, which may be themselves a proposition (P), a formula (P ∧ Q) or several connected formulae (φ ∧ ρ).

x, y, z             variables     Lowercase Roman letters towards the end of the alphabet are used to signify variables. In logical systems, these are usually coupled with a quantifier, ∀ or ∃, in order to signify some or all of some unspecified subject or object. By convention, these begin with x, but any other letter may be used if needed, so long as they are defined as a variable by a quantifier.

a, b, c, … z     constants           Lowercase Roman letters, when not assigned by a quantifier, signifiy a constant, usually a proper noun. For instance, the letter “j” may be used to signify “Jerry”. Constants are given a meaning before they are used in logical expressions.

Ax, Bx … Zx     predicate symbols     Uppercase Roman letters appear again to indicate predicate relationships between variables and/or constants, coupled with one or more variable places which may be filled by variables or constants. For instance, we may definite the relation “x is green” as Gx, and “x likes y” as Lxy. To differentiate them from propositions, they are often presented in italics, so while P may be a proposition, Px is a predicate relation for x. Predicate symbols are non-logical — they describe relations but have neither operational function nor truth value in themselves.

Γ, Δ, … Ω     sets of formulae     Uppercase Greek letters are used, by convention, to refer to sets of formulae. Γ is usually used to represent the first site, since it is the first that does not look like Roman letters. (For instance, the uppercase Alpha (Α) looks identical to the Roman letter “A”)

Γ, Δ, … Ω     possible worlds     In modal logic, uppercase greek letters are also used to represent possible worlds. Alternatively, an uppercase W with a subscript numeral is sometimes used, representing worlds as W0, W1, and so on.

{ }     sets     Curly brackets are generally used when detailing the contents of a set, such as a set of formulae, or a set of possible worlds in modal logic. For instance, Γ = { α, β, γ, δ }