# Tag Info

## New answers tagged propositional-calculus

1

Answer 1: Either $\neg q$ or $q$ is true. So at least one of $\neg p \vee \neg q$ and $p \vee q$ is true, so expression 1 is a tautology. Also $\neg q \vee q$ is always true. so expression 2 is also a tautology, so they are equivalent. Answer 2: \begin{align*} (\neg p \vee \neg q) \vee (p \vee q) &\equiv (\neg p \vee (\neg q \vee (p \vee q)) \\ ...

0

As long as you are using a sound deductive system, to prove $\phi\equiv\psi$ you have to assume $\phi$ then deduce $\psi$ from this assumption and assume $\psi$ then deduce $\phi$ from this assumption. Since a sound deductive system is truth preserving, this ensures that if $\phi$ is true then $\psi$ is true and if $\psi$ is true then $\phi$ will be true - ...

2

If with the term tautology you mean also a valid formula of first-order logic, the answer is : YES. In general, we have that : $\forall x \forall y \varphi$ and $\forall y \forall x \varphi$ are equivalent. Thus, $∀x∀y P(x,y) \to ∀x∀y P(y,x)$ is equivalent to $∀x∀y P(x,y) \to ∀y∀x P(y,x)$. In addition, you can "rename" the bounded variable without ...

0

Yes, for example you can use DeMorgan's laws: $$a \vee b = \neg((\neg a) \wedge (\neg b))$$ $$a \wedge b = \neg((\neg a) \vee (\neg b))$$ As well as distributivity over the operators: $$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$$ $$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$$ And there are a lot of more rules you can use to simplify ...

0

I'll deny the consequent and then show that the antecedent and such a denial leads to the empty set. from the antecedent 1 Cac from the antecedent 2 Cbc from the antecedent 3 Nc 1 clausify 4 ANac 2 clausify 5 ANbc deny the consequent 6 Aab 3, 4 resolve 7 Na 6, 7 resolve 8 b 3, 5 resolve 9 Nb 8, 9 resolve ...

0

Given the material implication X, X: if p is true, then q is true the possibilities are: A: p, q B: p, ¬q C: ¬p, q D: ¬p, ¬q The implication X is silent on the cases where p is not true (¬p or ~p in your notation), C and D above. X asserts that A, not B, is the case when p is true. A, above, represents the intersection of p and q, in set ...

0

Clearly, if the right hand side is true you have nothing to show. Assume that the right hand side is false. Then $A$ or $B$ is true. Use it to show that the in this case the left hand side is always false. If $C$ is true this is obvious, if $C$ is false then use the fact that $A$ or $B$ must be true.

2

Can't you just expand your first formula by adding more variables? For instance $$(a\to(b\to c))\to((a\to d)\to((b\to d)\to(c\to d))$$ or CCaCbcCCadCCbdCcd in Polish notation, should be an organic tautology if I'm not wrong.

1

There is no such thing as the sequent calculus (even for a particular logic, like -- to keep things simple -- classical propositional logic). There is a number of varieties. There is no such thing as the natural deduction calculus (for the same logic) either. But on any story, sequent calculi and natural deduction systems are different sorts of beasts ...

0

A propositional logic is said to be satisfiable if its either a tautology or contingency. Hence if a logic is a contradiction then it is said to be unsatisfiable. By contingency we mean that logic can be true or false i.e. nothing can be said for sure about the logic.

1


8

The question is more complicated then a simple ex falso quodlibet. If the sequence of letters makes sense at all, then it is true, since there is no one-to-one function $\mathbb{N}\rightarrow\{1, \ldots, 100\}$. However, it is not clear whether we are talking about a logical formula at all. For example $(\exists x: x\neq x)\Rightarrow (x+\forall)$ is not a ...

-1

Here are two ways to think about your question going back to the philosophy of logical reasoning: (1) If we trust that classical propositional-logic is an adequate account of truth-preservation in mathematical reasoning then, looking at the truth-table for the material-conditional in classical propositional-logic, we see that the material-conditional is ...

0

"It seems as though this should not be a valid statement" If it's not a valid statement, then either "f is a one to one correspondence" is true and "f−1(2)=3" is false, or both statements are false and "if p, then p" is false, where the truth value of the proposition "p" is false. It is not the case that ""f is a one to one correspondence" is true and ...

9

An instructor asked the class whether all cell phones in the classroom are shut off. If by some fluke, there are no cell phones in the classroom, then the answer is "yes". "Yes" means there are no turned-on cell phones in the classroom. Same thing here: there are no one-to-one correspondences from $\mathbb N$ into a set of only $100$ members; therefore, ...

3

The main focus on one or the other correspond to two different historical approaches of logic: In Frege's Begriffsschrift (1879), for example, logic is thought as a science, that is, a body of laws governing the notion of the Truth. Therefore, what is important for him is to hightlight the fundamental principles of thought and put them together, as the ...

3

A logical axiom can be be considered a rule of inference that happens to have with no antecedents. Any interesting proof system must have at least one axiom (otherwise there is no way to begin a proof in the empty theory), but it must also have at least one rule of inference with premises (otherwise all you could prove would be the axioms themselves). ...

4

Actually, Gentzen introduced two families of calculi, of which the more important perhaps are the natural deduction calculi (which Bruno Bentzen is referring to in his answer). Sequent calculi are rather different from both natural deduction calculi and Hilbert calculi. The latter are both ways of constructing arguments from propositions (wffs in the ...

3

You can see a very detailed overview into : Francis Pelletier & Allen Hazen, Natural Deduction : Sequent Calculus was invented by Gerhard Gentzen (1934), who used it as a stepping-stone in his characterization of natural deduction [...]. It is a very general characterization of a proof; the basic notation being $ϕ_1,\ldots,ϕ_n ⊢ ψ_1,\ldots,ψ_m$, ...

3

Both systems are equivalent in the sense that they proof the same theorems. A Hilbert-style deduction system uses the axiomatic approach to proof theory. In this kind of calculus, a formal proof consists of a finite sequence of formulas $\alpha_1, ..., \alpha_n$, where each $\alpha_n$ is either an axiom or is obtained from the previous formulas via an ...

1

In Rautenberg's approach, a substitution is a function $\sigma : PV \to \mathcal F$ defined on the set $PV = \{ p_0, p_1, \ldots \}$ of propositional variables (see page 4). Thus, the function is defined for all variables; assume, e.g. : $\sigma(p_0)=\alpha$ and $\sigma(p_i)=p_i$, for $i > 0$. Then, we have to apply the substituion $\sigma$ to a ...

1

Your understanding is not wrong (though you really ought to view substitution at least as something that can swap in an entire formula for your chosen variable, and writing $F\cup PV$ is a mistake since every propositional variable is in particular a formula), but it is a different angle on things than Rautenberg's (slightly more general) definition. In ...

2

The property you're looking for is generally a consequence of the logic being sound. The soundness theorem for a proof system states that everything it can prove (from a given theory) is true in every interpretation of the logical language (that satisfies each of the theory's axioms). In particular, once you know a logic to be sound, you know it cannot ...

Top 50 recent answers are included