Trying to get my logic terminology straight

118 Views Asked by At

I am having some trouble wrapping my head around the specific definitions of things when it comes to logic. This is my current understanding from my own note-taking, can anyone correct me?

Expressions: $2+2$, for example. Any sequence of mathematical symbols which produce some mathematical object like a number, matrix, function, set, etc.

Statements: Usually made up of expressions and must evaluate to either true or false. Statements must be well-formed. Not invoking undefined behavior like $0/0=1$ or bad syntax like $==3++-4=-$. So $2+2=4$ is a true statement, $2+2=5$ is a false statement. Statements are allowed to contain words and properties, e.g. "$30+7$ is prime".

Relations: Symbols like $=$, $<$, $\leq$, $\in$, $\subset$, etc, which provide some relationship between expressions to create a statement.

Properties: Is prime, is continuous, is invertible, etc.

Logical Connectives: And, or, not, if-then, implies, if-and-only-if, etc. These connect statements to create "compound statements" which are themselves still statements.

Compound Statement: For statements $P$ and $Q$, things like $P \land Q$, $P \lor Q$, $P \implies Q$, $P \iff Q$, etc.

Proposition: I don't really understand the difference between this and a statement but I am guessing $2+2=4$ is also a proposition, or something like "John has brown hair."

Predicate: Like a proposition but with variables, may be true or false depending on the value of the variable. For example $P(x) = x + 2 = 5$ is true when $x=3$ and false otherwise.

Quantifier: The universal quantifier $\forall$, or the existential quantifier $\exists$.

Universe: The relevant set of objects we draw from, referred to via quantifiers. For example $\forall x \in \mathbb{N}$ means "for all $x$ in the natural numbers", the natural numbers here would be the universe.

Is my understanding correct so far?

1

There are 1 best solutions below

10
On BEST ANSWER

Pretty good. Personally, I would do 'predicates' a little different. The $P$ would be the predicate, while $P(x)$ would be a formula.

Also, you can regard properties as $1$-place predicates, and relations as $n$-place predicates. For example, $\le$ is a $2$-place predicate, and $\le(x,y)$ would be a formula using that predicate. ... though we will often use the infix notation $x \le y$ instead.

Indeed, the notion of a 'formula' is important but missing from your list. You can create Atomic formulas by giving an $n$-place predicate $n$ terms, which can either be constants (like $1$), variables (like $x$), or complex terms (like $x+1$). Atomic formulas can be combined using logical connectives into 'compound formulas', and formulas can be quantified.

Statements are formulas that do not have free (i.e. unquantified) variables).