Propositional/Predicate Logic Louis Greenfield

Syntax
Axioms
1. Axiom 1.1 [Commutativity]
2. Axiom 1.2 [Associativity]
3. Axiom 1.3 [Distributivity]
4. Axiom 1.4 (De Morgan)]
5. Axiom 1.5 [Negation}
6. Axiom 1.6 [Excluded Middle]
7. Axiom 1.7 [Contradiction]
8. Axiom 1.8 [Implication]
9. Axiom 1.9 [Equality]
10. Axiom 1.10 [or-simplification]
11. Axiom 1.11 [and-simplification]
12. Axiom 1.12 [Identity]
  1. Whatever is, is
Essential Connectives
1. Negation
  1. NOT
2. Conjugation
  2. AND
3. Disjunction
  1. OR
4. Conditional
  1. IF (...) THEN / IMPLIES
5. Biconditional
  1. EQUIVALENT / IF AND ONLY IF
Fundamental Concept
1. In propositional logic a statement (or proposition) is represented by a symbol (or letter) whose relationship with other statements is defined via a set of symbols (or connectives).
  1. "If it rains, Elliot won't go to school." A: It rains B: Elliot won't go to school
  2. "We will cancel the parade if and only if it rains" A: We will cancel the parade B: it rains
2. The statement is described by it's truth value which is either true or false.
  1. T
  2. T
  3. T
  4. T
  5. F
  6. F
  7. F
  8. T
  9. T
  10. F
  11. F
  12. F
T
T
T
F
T
F
F
T
F
F
F
T
Predicate Logic
1. Syntax
2. Structure
Quantifiers
1. The Universal Quantifier
  1. guarantees that a predicate applies to all members of the universe of discourse.
    1. UD: All people Hx: x is happy
    2. everyone is happy
2. The Existential Quantifier
  1. guarantees that the quantified predicate applies to at least one of the members of the universe of discourse.
    1. UD: people in this room Dx: x can dance
    2. there exists someone (at least one), who can dance.
Status
1. Tautology
  1. Propositions, which must be true, under every possible valuation.
    1. "It is either raining or not raining."
2. Contradiction
  1. Proposition which must necessarily be untrue, under every possible valuation.
    1. "It's raining and it's not raining"
3. Contigency
  1. Proposition that are nor true, nor false under every possible valuation. A proposition is contingent if and only if it is neither a contradiction nor a tautology.
Structure
1. Atomic formulas
  1. Atomic formulas is a formula that contains no logical connectives nor quantifiers, or equivalently a formula that has no strict sub formulas, making them the simplest "wff" (look at def below) in logic. In propositional logic an atomic formula or atom is simply a propositional variable that is either true or false.
    1. A: Elliot likes cheese . B:
2. Well-formed formulas
  1. We can construct much more complex propositions by combining atomic formulas with connectives, these constructions are called well-formed formulas (wff) when they respect the following set of rules:
    1. 1) If A is a well formed formula, then ¬A is also a well formed formula. 2) If A and B are well formed formula's, then (A∧B) is also a well formed formula. 3) If A and B are well formed formula's, then (A∨B) is also a well formed formula. 4) If A and B are well formed formula's, then (A→B) is also a well formed formula. 5) If A and B are well formed formula's, then (A↔B) is also a well formed formula. Unless constructed using only 1-5 above, then a proposition isn't a well formed formula.
      1. is a "wff"
      2. is not a "wff"
Conditions
1. Validity
  1. There are two ways an argument can go wrong: 1) The premise is wrong 2) The logical structure of the argument is wrong. In propositional logic, we cannot do anything to determine whether the premise is actually true, so we define the validity of an argument in terms of the second idea.
    1. {P1, P2, ... , Pn} is said to entail C, if and only if there is no truth assignment for which P1, P2, ... , Pn are true and C is false.
2. Consistency
  1. A set of propositions is inconsistent if it cannot be simultaneously all true. Otherwise, it is consistent.
    1. is inconsistent if and only if
      1. is a contradiction
What is Logic ?
1. Logic is a truth-preserving system of inference.
  1. Truth-Preserving:
    1. If the initial statement are true, the inferred statements will be true.
  2. System
    1. A set of mechanistic transformations, based on syntax alone.
  3. Inference
    1. The process of deriving (inferring) new statements from old statements.
The "=" Identity
1. The "=" identity is actually a two place predicate which tells us that a given term can always be replaced by the other.
  1. UD : All people. Sx : x is a spy; Txy: x is taller than y; l: liz
    1. This says: liz is the tallest of all spies.
Fundamental Concept
1. Predicates
  1. A Predicate expresses a relation or property and is combined with variables that expresses an arbitrary value of some domain.
    1. Ax: x is tall; Bxy: x owes money to y; Cxyz: x borrowed y from z.
    2. The predicates with one argument, two arguments, or in general n-arguments are referred to as monoadic, dyadic or n-adic respectively.
    3. Conventionally, we denote the predicates with capital letters, the variable arguments with x, y, z ... and constants with lowercase letters (a, b, c ...).
Enumeration using Identity and Quantifiers
1. Let Px be some predicate. Using quantifiers we start expressing several ideas of quantity.
  1. At least (one)
    1. At least (two)
  2. Exactly (one)
    1. Exactly (two)
  3. At most (one)
    1. At most (two)
logical laws
1. If a propositional component appears in a logical sentence and each occurrence of this component is replaced with a more specific propositional sentence, then the result is also a logical law, this phenomenon is called De Morgan's Law. Greek letter are conventionally used to represent propositional sentences.
Logical Laws
1. De Morgan's Laws (DML)
2. Commutative Laws
3. Associative Laws
4. Idempotent Laws
5. Distributive Laws
6. Double Negation Law
7. Tautology Law
8. Contradiction Law
9. Conditional Laws (CL)
10. Contrapositive Law
11. Biconditional Law
Structure
1. Atomic fromula's
  1. The precise definition of the atomic formula varies in different types of logic, since predicate logic is an extension of propositional logic all the previous notions (truth table, connectives...) still apply and new notions will be added to the definition of the atomic formula. Instead just using propositional letters, and atomic formula is now one that has predicates and is quantified by quantifies ( and still connected by connectives).
    1. Axy : Elliot likes x and y. Byz: Edie and y both like z. Bzy: Edie and z both like y.
2. Well-formed formula's
  1. The syntax for wff in predicate logic are quite similar to the ones of propositional logic except that we include quantifiers.
    1. (1,2,3,4,5) : same as Propositional logic. 6) If A is a well formed formula, and x is a variable, A contains at least one occurrence of x, and A contains no x quantifiers, then ∀xA is also a well formed formula. 7) If A is a well formed formula and x is a variable, A contains at least one occurrence of x, and A contains no x quantifiers, then ∃xA is also a well formed formula
Definite / indefinite descriptions
1. Descriptions which are not suitable for representing a constant in predicate logic are indefinite descriptions.
  1. In the sentence : "some dog is annoying" , "some dog" is an indefinite description.
2. All other descriptions are definite. If there is something that actually fits the description of the term,
  1. the fitting object is called the referent of the term. However, it is possible to construct sentences with terms that do not refer to anything, in which case the term itself is called a non-referring term.
The need for Quantifiers
1. How does one say : "Everyone in this class is a Student" using propositional logic + predicates ? Here are some possible approaches:
  1. We could use a single proposition such that P ="everyone in this class", but that's not very useful because the proposition is very dense (says a lot) and can't be broken down into smaller pieces which gives it less flexibility when put in context. The fact that this is pretty much our only option using only propositional logic illustrates it's short comings.
  2. We could break down the statement into two proposition and predicates : Px: x is in the class. Gx: x is a student. and write a statement :
    1. However with two proposition for each person in the class, this becomes quite exhausting, especially with larger sets that have multiple propositions.
Universe of discourse
1. In logic, an argument is defined over a universe of discourse (UD). Every argument and statement made in that within a universe applies to all the entities of that universe.
2. In Natural languages we out of convenience deduce a universe of discourse based on context, for example let's say someone is talking about how much they love vegetables, we assume that the statement is applied to all vegetables and not all fruits.
3. With the help of quantifiers we can troubleshoot some of the inconveniences and short comings we saw appeared in propositional logic.
  1. A possible solution to the statement "Everyone in this class is a Student" using the universal quantifiers.
    1. UD: Everyone
The Uniqueness quantifier
1. The uniqueness quantifier refers to the ability of an object to be the only of it's kind to satisfy a certain condition.
2. Notation
  1. can be translated in terms of universal and existential quantifier. In Logic, like in natural languages ,there are different ways you can phrase a sentence and still convey the same meaning. Here are two of my favorite statements that describe the uniqueness quantifier.
    1. You can also play around with the Negation of the Uniqueness quantifier:
      1. This can be interpreted as : "there does not exists at all or there exists but without uniqueness", now if that's not a beautiful sentence !