您在這裡

Glossary

17 六月, 2015 - 10:08
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/383d4b87-2d7b-454e-99fe-2eaa43eae8ff@20.20

C     completeness

If something really is true, the system is capable of proving it.

connective

  1. The syntactic operator combining one or more logical expressions into a larger expression.
    1. Example: Two operators are ∧ and ∨.
  2. A function with one or more Boolean inputs and a Boolean result. I.e., the meaning of a syntactic operator.
    1. Example: The meaning of ∧ and ∨, e.g., as described by their truth tables.
    2. Example: nand (mnemonic: "not and"), written ↑, takes in two Boolean values a and b, and returns true exactly when a b is not true that is, a b ¬ (a b).

I     Interpretation

The interpretation of a formula is a domain, together with a mapping from the formula's relation symbols to specifc relations on the domain.

P     proposition

A statement which can be either true or false.

Example: "Your meal will include hashbrowns."

propositional variable

A variable that can either be true or false, representing whether a certain proposition is true or not. Example: HB

S     soundness

If the system (claims to) prove something is true, it really is true.

T     tautology

A WFF which is true under any truth assignment (any way of assigning truejfalse to the propositions).

Example: A − unsafe ⇒ A − unsafe

Example: aab

term

  1. A variable. Example: a, b, ...
  2. A constant. Example: WaterWorld location F , Kevin Bacon, or the number 3.
  3. A function applied to one or more terms.

Example: successor (3)

truth assignment

An assignment of a value true or false to each proposition being used.

Example: For the formula aab, one possible truth assignment is a = true and b = false. With that truth assignment, the formula is false.

truth table

A truth table for an expression has a column for each of its propositional variables. It has a row for each different true/false combination of its propositional variables. It has one more column for the expression itself, showing the truth of the entire expression for that row.

U     unsatisfable

A WFF which is false under any truth assignment.

Example: ¬ (A unsafe A unsafe)

Example: a ⇒¬a

W     well-Formed formula (WFF)

  1. A constant: true or false. (If you prefer brevity, you can write T or F.)
  2. A propositional variable.
    1. Example: a
  3. A negation ¬φ, where φ is a WFF.
    1. Example: ¬c
  4. A conjunction φψ, where φ and ψ are WFFs.
    1. Example: a ∧¬c
  5. A disjunction φψ, where φ and ψ are WFFs.
    1. Example: ¬ca ∧¬c, or equivalently, (¬c) ∨ (a ∧¬c)
  6. An implication φψ, where φ and ψ are WFFs.
    1. Example: ¬ca ∧¬cb, or equivalently, ((¬c) ∨ (a ∧¬c)) ⇒ b

Well-Formed Formula (WFF) for first-order logic

  • A constant: true or false.
  • An atomic formula: a relation symbol applied to one or more terms.
    • Example: nhbr (x, F )
  • A negation of a WFF, ¬φ.
  • A conjunction of WFFs, φψ.
  • A disjunction of WFFs, φψ.
  • An implication of WFFs, φψ.
  • A universal quantifcation of a WFF, ∀x :(φ).
    • Example: ∀x : (nhbr (x, F ))
  • An existential quantifcation of a WFF, ∃x :(φ).
    • Example: ∃x : (nhbr (x, F ))