Tag Info

New answers tagged

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

First note that $$(p\land r)\rightarrow (q\lor s)$$ $$\equiv\neg (p \land r) \lor (q\lor s)$$ $$\equiv(\neg p \lor \neg r) \lor (q\lor s)$$ $$\equiv\neg p \lor \neg r\lor q\lor s$$ $$\equiv(\neg p \lor q)\lor(\neg r\lor s)$$ $$\equiv(p \rightarrow q)\lor(r\rightarrow s)$$ Therefore $$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land ...


0

If we take a look at say the Schaum's Outline of Logic, it states one rule of conjunction elimination as "From a conjunction, we may infer either of its conjuncts." Thus, given two wffs the output of conjunction elimination is not unique and thus not a function. Also, if we were to reason from Cpq, Crq, Apr to q we would call that a use of disjunction ...


1

In general, we have $$(A\implies B)\iff(B\lor\lnot A)$$ and $$(A\land B)\implies (A\lor B)$$ Applying the first of these, we get $$((p\implies q)\land(r\implies s))\iff((q\lor\lnot p)\land(s\lor\lnot r))$$ Applying the second, we get $$((q\lor\lnot p)\land(s\lor\lnot r))\implies((q\lor\lnot p)\lor(s\lor\lnot r))$$


1

Of course both are satisfiable: Recall that a set of sentences $S$ is complete if, for every sentence $\varphi$, either $S \vdash \varphi$ or $S \vdash \neg \varphi$. All we need to show is that not every finite satisfiable set is complete. That is, as observed in the comments, it suffices give a counterexample of an incomplete finite satisfiable set. And ...


0

I use Lukasiewicz/Polish notation. So, we know that CpCqp is a tautology. Thus, CpCqp is logically equivalent to CpCNqp, since it qualifies as a special case of CpCqp (substitute 'q' with 'Nq' in CpCqp). One equivalence says that CNxy == CNyx, where x and y are wffs. Thus, since CpCNqp is logically equivalent to CpCNpq. The law of commutation says ...


-1

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\rightarrow} ...


1

Use that $a\rightarrow b$ is equivalent to (or, in fact, defined to be) $(\neg a)\vee b$ and write out both sides.


2

Your doubts are justified. For $R$ to be reflexive, you must have $(A,A)\in R$ for all propositions $A\in\Omega$. But you don't. Whenever $A$ is false, you have $A\land A = 0$. Therefore $A\not\in R$.


1

You have discovered the same problem that Kracht discusses in "The Mathematics of Language", chapter 4, section 5, the variable $y$ is dependent on $x$ in the sentence $(\forall x, \exists y(x), R(y(x),x))$. (Kracht does not originate this observation; this is just a discussion of the difficulty which I have read.) You appear to be re-inventing the ...


1

First, note that - as was said in the comments - the problem is not always solvable: There is no $F$ such that $(x\vee y)\vee F=x$. (No matter what $F$ is, the assignment $y=True, x=False$ will always satisfy the left side and not the right.) There is no $G$ such that $x\wedge G=y$. ($x\wedge G$ always implies $x$, while $y$ doesn't.) We can rephrase ...


0

I'm still not sure what you're asking for. Does this answer your question? $ \begin{eqnarray*} y \vee z &\equiv& ((x \Rightarrow y) \wedge (\neg x \Rightarrow y)) \vee z \\ &\equiv& ((\neg x \vee y) \wedge ( x \vee y)) \vee z \end{eqnarray*}$


2

Hint. Consider the theory $\{\neg p\mid p\in\Sigma\}$. Your assumption amounts to saying that this theory is inconsistent. By compactness, therefore, it has a finite inconsistent subset $\{\neg p_1,\neg p_2,\ldots,\neg p_n\}$.


0

$(\neg p\wedge\neg q)\vee(p\wedge q)=\neg((p\vee q)\wedge\neg(p\wedge q))=\neg((\neg p\wedge q)\vee(p\wedge\neg q))=(p\vee\neg q)\wedge(\neg p\vee q)$


0

Using a table of truth you can prove that: (1) w $\vee$ (p $\wedge$ q) ≡ (w $\vee$ p) $\wedge$ (w $\vee$ q) Hint: use w = (~p ∧ ~q). Here follows the steps (2) (~p ∧ ~q) ∨ (p ∧ q) ≡ ((~p ∧ ~q) $\vee$ p) $\wedge$ ((~p ∧ ~q) $\vee$ q) Using (1) we can say that (~p ∧ ~q) $\vee$ p ≡ (~p $\vee$ p) $\wedge$ (~q $\vee$ p) as (~p $\vee$ p) its a tautology, ...


0

Propositional Calculus Use de Morgan's rules. Start like this: $$(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee (p \wedge q)) \wedge (\neg q \vee (p \wedge q))$$ Now apply them again inside the parentheses and remove tautologies. Then you're done. Truth table You can make a truth table with two variables and two outcomes. It will have four ...


1

Assuming you have this in your arsenal, try using a "first-inside outside-last" distribution for the propositions. Then simplify. That is, think of it like addition and multiplication: $(a+b) \cdot (c+d) = (a \cdot c) + (a \cdot d) + (b \cdot c) + (b \cdot d)$. If that isn't allowed, try using truth tables as a simple way of approaching it.


0

Note that $(p→(q→r))→((p→¬r)→(p→¬q))$ is a tautology. There's a typo in your wolfram input. It should look like this, with the $r$ in $(p \rightarrow \neg r)$ negated. But your simplification is correct. It can be further simplified though.


1

If I can add something: The De Morgan's Laws holds exclusively for conjunction and disjunction, thus having something to do with their duality. It is a pair of laws, expressed informally as follows: The negation of a conjunction is the disjunction of the negations. The negation of a disjunction is the conjunction of the negations. Symbolically: ...


1

Example, as requested... Suppose I want to know what is the domain of the function $$ \frac{1}{x^2-4x+3} $$ That is, I want to find all the $x$ where that denominator is not zero. So I factor the denominator. $x^2-4x+3=(x-1)(x-3)$. When is it zero? Either $x=1$ or $x=3$. So when is it nonzero? $$ \neg\;\big(x=1\;\lor\;x=3\big) $$ That is, (by the ...


3

No, that does not work. What does work is De Morgan's law: $$ \neg(p\lor q) \iff \neg p \land \neg q $$ Your formulation is missing the negations on the right-hand side. If you want, you can think of this as "negation distributes over $\land$ and $\lor$, except that it changes each of them to the other". I'm not entirely sure that's a helpful way of ...


1

$p:=$ he is playing piano $1:=$ he is playing guitar $r:=$ he is asleep So the second raw means in the situation that ($p$) he is playing piano, ($q$) he is playing guitar and ($\lnot r)$ he is not asleep, then the given proposition of the problem is valid.


2

The confusion: p → q, is true in all cases except when p is true and q is false. In the above problem, if x < 0 is true then x² > 0 will be true. But, when, x = 0, then, the premise x < 0 is false. But, according to definition, if premise is false, the expression is still considered true. Doesn't it contradict? Where the antecedent of an ...


0

If both of them are killers, that means that both the first and the second witness tell lies, so the third one tells a lie, which works perfectly fine with the system, so yes you are correct. Specifically, the definition of "at least" is basically "greater than or equal to", so the opposite would basically be everything previously ignored, or "less then". ...


2

The prover online http://tassi.web.cs.unibo.it/logic/ should help you to understand the intuitionistic proof in sequent calculus (G3ip) for $\neg \neg (\neg P \lor P)$. In fact this formula is provable in minimal logic i.e. a subsystem of intuitionistic logic. Note that the proof below (produced by the prover for G3ip that I just mentioned) does not really ...


0

This problem must have been intended as torture, because the answer is: you won't get to p (a horrible thought, isn't it? :). The only nonconditional proposition you're given is r, which leads nowhere. The only other option is indirect proof in which you assume ~p and try to derive a contradiction. But that also leads nowhere, because you can't apply ~p to ...


3

You won't be able to derive $p$ from the hypotheses. There are a couple of ways you can see this, but the easiest might be to realize that, if the hypotheses are true, then you should be able to conclude that $p$ is true. Here, $p \to q$, $\lnot q \to r$, and $r$ being true are not enough to coerce $p$ to be true, since these conditions are satisfied if ...


-1

Hint : You can make a truth table, and take p and q values as true and r as false


1

I'm having a hard time understanding this proof. Why is it necessary to state line 5? If you have $A\vee B$ and wish to show it proves $C$ -- that is $A\vee B\vdash C$ -- then you may use Disjunctive Elimination. Disjunctive Elimination is the rule that: $$A\vee B, A\to C, B\to C \vdash C$$ So Lines 2 and 5 are where you take(assume) two halves ...


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