Tag Info

New answers tagged

0

Your left-hand side conjunctor is ok, but not the right-hand side one, as Mauro commented. $$ (ϕ→(ψ∨¬X))∧(ϕ→(ψ∧X)) \iff ((¬(ϕ∧(¬ψ∧X))∧\underbrace{\color{}{(¬ϕ∧¬(ψ∧X))}}_{¬(ϕ∧¬(ψ∧X))})$$ Recall the equivalences we need: $ \alpha \rightarrow \beta \equiv \neg (\alpha \land \neg \beta)$ $ \alpha \lor \beta \equiv \neg (\neg \alpha \land \neg \beta)$ ...


1

Here's how to think about it colloquially: $\neg Q\vee R$ is a problem - does $\neg Q$ hold or does $R$ hold? - and the hypothesis $Q$ resolves the problem, resulting in a formula ("$R$") not containing $Q$. Technically, this is an example of "resolution": http://en.wikipedia.org/wiki/Resolution_inference. The notation is a bit weird, but what's going on is ...


1

First, "unless" is not formal mathematical language. It is loose terminology. Read it longer as "$q$ is true unless $p$ is false." This is read as "either $q$ is true or $p$ is not true." If this is true, and $p$ is true, it in necessarily the case that that $q$ is true.


1

Suppose: "If $p$, then $q$." There are two cases: $p$ can be true, or it can be false. If $p$ is true, then so is $q$. So it follows that $q$ holds unless $p$ is false. Ergo, $q$ unless not $p$. Now suppose: "$q$ unless $\neg p$." We're trying to prove "If $p$, then $q$." So assume $p$. Since its not the case that $\neg p$ holds, hence from "$q$ ...


0

It doesn't! "p implies q", $p\to q$ is equivalent to "q or not p", $q\vee \neg p$.   This is an inclusive or; it does not exclude the possibility that $q$ and $\neg p$ may be both true. That is not the same thing as "q unless not p", which would be an exclusive or.


2

As complement to the answer above, I would suggest you to begin with: Hodges & Chirswell's Mathematical Logic (2007) - The very book begin by taking an informal exposal of natural deduction in Chapter 2 before they got more serious on the subject taking the propositional (p.53) and first-order calculus (p.177) After you get some feeling of it, maybe ...


1

We have the premises: $\Gamma=\{A∧(B∨C),(¬C∨H)∧(H→¬H),¬B\}$ Notice the second premise is a conjunction and the second half of that is: $H\to\neg H$. This will lead to a contradiction if $H$ is true. Notice the first half of the conjunction: $\neg C\vee H$. $H$ will be true is $C$ is true. Put the conjunction together and we will have a contradiction if ...


3

The conclusion is not a premise.   You can't use it to prove itself; that's circular reasoning.   Circular reasoning is bad because circular reasoning is bad. $$\begin{array}{l|lr} 1- & ¬N &\text{Premise} \\ 2- & (¬N → L) \wedge (D ↔ ¬N) &\text{Premise} \\ 3- & ¬N → L &\wedge \text{ ...


2

Whenever we have one of these let's look at what we know assuming the system is consistent. We know: $\neg B$ and $A\wedge (B\vee C)$ so using $\wedge$-elimination we know $(B\vee C)$ If $B$ were true then we would get a contradiction, namely $\neg B$ and $B$. So $C$ must be true. Using a similar process you can show $H$ must be true. Once you know this ...


0

To reiterate my assumptions: I assume we are trying to derive a contradiction from this set of sentences? i.e. inconsistent means that at least one of these sentences must be false. From $A\wedge ( B \vee C)$, we have $B\vee C$. Since $\lnot B$, we have $C$ by disjunctive syllogism. Therefore since $(\lnot C \vee H)\wedge (H\implies \lnot H)$, we have ...


1

We have the following deduction: 1) $L\rightarrow(\lnot L)$ by hypothetical syllogism and P2,P3. 2) $(\lnot L)\vee(\lnot L)$ by material implication and 1. 3) $\lnot L$ by disjunctive tautology and 2. 4) $E\vee (L\vee M)$ by conjunctive simplification and P1. 5) $(E\vee L)\vee M$ by disjunctive associativity and 4. 6) $(L\vee E)\vee M$ by disjunctive ...


2

Get the contra-positives of 1&2 as $\neg B\rightarrow \neg A$ and $\neg C \,\,V\neg D \rightarrow \neg B$. Use $\neg C \,\,V\neg D \rightarrow \neg B, \,\,\,\, \neg B \rightarrow \neg A$ and the result follows.


1

Truth Table is my favorite option As you can see. LHS=RHS


0

An other approche (I'll use set theory). Let $A,B$ two set and suppose $A\subset B$ and let $x\in A$. Then, by hypothesis, $x\notin A\cap B^c=\emptyset$. Therefore, $x\in (A\cap B^c)^c=A^c\cup B$. Reciprocally, if $x\in A^c\cup B$ then $x\notin A\cap B^c$, then if $x\in A$, then $x\notin B^c$ and thus $x\in B$. That mean $A\subset B$. If $x\in B^c$ then ...


0

I highly recommend avoiding "p∧q∧r" and the like when talking in a proof-theoretic context. In a proof-theoretic context a proof is a sequence of well-formed formulas (wffs). I can tell which wff p∧(q∧r) stands for and I can tell which wff (p∧q)∧r stands for (neither of those strings are wffs). But, I can't tell which wff p∧q∧r stands for. It could mean ...


-1

Informally, one might say that if three things are true ($p \land q \land r$), then also one thing and two things — $p \land (q \land r)$ — and two things and one thing — $(p \land q) \land r$ — are true. In a formal deductive system commonplace in symbolic logic, we want to be more formal. We usually deduce consequences from a set ...


0

Yes, you are right: conjunction is associative. Thus, it doesn't matter where you put the parentheses. Hence, when you see "$p \land q \land r$", it means that you may insert the parentheses anywhere and you will get the same result.


0

Dual Negation: $$\neg \forall x\in S : P(x) \;\iff\; \exists x \in S:\neg P(x) \\\neg \exists x\in S : P(x) \;\iff\; \forall x \in S:\neg P(x)$$ When in doubt, take it one step at a time. So "not $\forall$ odd integers n, $\exists$ integer $k$ such that $n=2k+1$" Becomes "$\exists$ odd integers n, not $\exists$ integer $k$, such that $n=2k+1$" Then ...


1

$a)$: For any odd integer $n$, there is some integer $k$ such that: $n = 2k+1$, $b)$: There is a real number $m$ such that for any real number $n$: $m\times n = n$.


0

Suppose that for each $k$ there is a truth assignment for $\Sigma$ which makes all of $p_1,\ldots,p_k$ false. In other words, $\Sigma \cup \{ \lnot p_1, \cdots, \lnot p_k \}$ is satisfiable. This means that every finite subset of $\Sigma \cup \{ \lnot p_i : i \geq 1 \}$ is satisfiable, since for every such finite subset there is a maximal index $k$ such that ...


0

It is called a tautology. You may look at the wikipedia page http://en.wikipedia.org/wiki/Tautology_%28logic%29


1

It's usually called $1$. If you call your truth values something else, then the name changes accordingly.


0

See also K-map: http://en.wikipedia.org/wiki/Karnaugh_map It is a very clever and fast method to derive DNF and other useful things


1

$n$ propositions $\phi_1,\phi_2,\ldots,\phi_n$ are said to be contradictory when their conjunction is a contradiction, i.e. a logical falsehood: $\overline{v}\left(\bigwedge_{k=1}^{k=n}\phi_k\right)=F$. In your case, build the conjunction of your three propositions and check if it is possible for it to be true - if not, the three propositions are ...


2

If you have proved the Deduction Theorem for your Hilbert-style calculus, you know that the premises $S\cup\{\alpha\}\vdash\beta$ and $S\cup\{\neg\alpha\}\vdash\beta$ imply, respectively, $S\vdash \alpha\to\beta$ and $S\vdash\neg\alpha\to\beta$. Now $(\alpha\to\beta)\to((\neg\alpha\to\beta)\to\beta)$ is a classical propositional tautology. You ought to have ...


0

Of course, we can use also the tableau method, obtaining the same result produced by the use of truth-table. We have to apply the tableau to the original formula, checking its satisfiability. Each open path defines a (set of) assignments to the sentential variables satisfying the formula. Every assignment will form a "basic conjubct" that must be ...


0

Note that you can rewrite $p\to\neg(q\lor r)$ as $\neg p\lor(\neg(q\lor r))$, i.e. $\neg p\lor(\neg q\land\neg r)$. This fits exactly the truth table (as you would expect), and shows that the proposition is true whenever $p$ is false or both $q$ and $r$ are false. This would usually enough be enough to answer your question, but we can also give a full ...


1

I am assuming you mean truth table in the title. Consider a conjunction of literals such as $p \land \lnot q \land \lnot r$: this is true for the assignment given by the row with $(p, q, r) = (1, 0, 0)$ in the truth table and not for any other row. The DNF is the disjunction of the conjunctions corresponding to the rows in which your formula is true. $$ ...


3

From the truth table \begin{align} p && q && p \leftrightarrow q \\ 0 && 0 && 1\\ 0 && 1 && 0\\ 1 && 0 && 0\\ 1 && 1 && 1 \end{align} pick those lines where the $p \leftrightarrow q$ is true and connect them with disjunctions: $$(\neg p \wedge \neg q) \vee (p \wedge q) =:F $$ ...


2

You can make use of Distributivity: \begin{align} (\neg p\vee q) \wedge (\neg q\vee p) & = ((\neg p \vee q)\wedge \neg q) \vee ((\neg p \vee q) \wedge p) \\ & = (\neg p \wedge \neg q) \vee (q\wedge \neg q) \vee (\neg p \wedge p) \vee (q\wedge p) \end{align} Of course, you can eliminate some of the terms in here, like $\neg p\wedge p=0$ and $\neg ...


1

Note: This procedure assumes you are referring to a propositional language $$L_V=\left<V,\rightarrow,\bot \right>$$ where $V$ is the set of proposition symbols of $L_V$. $L_\Sigma^*$ denotes the set of all strings of $L_V$. Hint: We are going to define the set of positive formulas of $L_V$, call it $POS_{L_V}$: Definition: The set POS of ...


2

Given some proposition $q$, consider the set of propositions $M(q)$ formed as follows: $T \in M(q)$ $F \in M(q)$ $q \in M(q)$ $ \forall \{e_w,e_x,e_y,e_z : (e_w \in M(q) \land e_x \in M(q) \land e_y \in M(q) \land e_z \in M(q)) \implies N(e_w,e_x,e_y,e_z) \in M(q)$ What we need to prove is that $\lnot q \not \in M(q)$ . To do that, consider a subset ...


2

Sketch solution/hint: So the only thing you need to prove (in this simple) when you want to show that it can not express $\neg$ is that for some valuation (i.e. line in a truth table), things do not work correctly. So what if we choose the valuation function $v$ which evaluate all propositional variables $p$ as $v(p)= true$ (i.e. the top line of a truth ...


3

If we agree that "to have a proof of $\alpha$", i.e. $\vdash \alpha$, means : there is a sequence of formulae $\phi_1, \ldots, \phi_n$ such that $\alpha=\phi_n$ and that formula in the sequence is a logical axiom or is derived from previous formulae in the sequence by modus ponens, this amounts to the "special case" of derivation from assumptions : ...


1

As said in the comments, you don't need to split the second premise. Here you can use the conjunction elimination ($X\land Y \vdash X$, $X\land Y \vdash Y$), conjunction introduction ($X,Y\vdash X\land Y$) and modus ponens ($X,X\rightarrow Y\vdash Y$). If I number you premises : $(V\rightarrow \neg W)\land (X\rightarrow Y)$ $\neg W\rightarrow Z$ $V\land ...


0

Hint We have to prove it using the definitions of satisfiability, logical consequence, etc. Consider one case : (i) $\implies$ (ii), and consoder the subcase : $\implies$ of (ii). We have : (i) $ \ \Gamma$ is satisfiable iff every finite subset of $\Gamma$ is satisfiable and we assume that : $\Gamma \vDash \alpha$. We want to prove that : ...


1

To transform the formula to DNF, go through the following steps: Write a truth table which shows the function value for all $2^n$ possible input combinations Take the truth table rows for which the function value is $false$ Invert the inputs in each of the rows from step 2. The result is a set of disjunctions which together constitute a DNF To get the ...


2

I use Polish notation. Np is equivalent to Cp0. Kpq is equivalent to NCpNq, which by the above is equivalent to CCpCq00. Apq is equivalent to CNpq, which by the above is equivalent to CCp0q.


0

We would read this as "Not (P or Q) is equivalent to Not P and Not Q". The prove is perhaps better understood in context of sets P and Q where "Not" means "Complement", "And" is "Intersection" and "Or" is "Union". We can then interpret the statement as $(P \cup Q)^C = P^C \cap Q^C.$ We then prove by showing that each side (set) is a subset of the other. ...


1

We can prove it by just drawing out a truth table $$\begin{array}{c|c|c|c|c|c|c} p&q&p\vee q&\sim p&\sim q&\sim(p\vee q)&\sim p\wedge\sim q \\\hline 0&0&0&1&1&1&1 \\0&1&1&1&0&0&0 \\1&0&1&0&1&0&0 \\1&1&1&0&0&0&0 \end{array}$$ We are done ...


0

The proposition says that if the combination ($p$ or $q$) is false, that is, if neither $p$ nor $q$ is true, then both $p$ is false and $q$ is false. You should imagine parentheses around the $\sim p$ and around the $\sim q$ on the right hand side. The $\vee$ means "or, and the $\wedge$ means "and". The proof depends on the system of axioms you start from, ...


0

It means not(~) (p or($\vee$) q) is equivalent to not(~) p and($\wedge$) not(~) q. It's called DeMorgan's law. You can use simple truth table to prove it.


1

From what I stated previously elsewhere: I assume you are referring to a propositional language $L_V=\left<V,\rightarrow,\bot \right>$, where $V$ is a set, called the proposition symbols of $L_V$. Now let $L_\Sigma^*$ denote the set of all strings of $L_V$. The usual definition of the set of well-formed formula of $L_V$, call it ...


1

You need to think about what it means to find a formula $x$ that fits the truth table. The easiest way to generate such a formula is simply to write a disjunction of all the cases where you want $x$ to be true. Essentially, $x$ will say "I am true when this combination of $A$, $B$ and $C$ occurs, or when that one occurs, or when that one occurs, etc.". What ...


1

because there are fewer $f$ than $t$'s, i will look at $$\begin{align}x &= ab'c'+ab'c++abc\\ &=ab'(c+c')+abc\\ &=ab'+abc\\ &=a(b'+bc)\\ &=a(b'+c)\end{align}$$


3

$x$ is only True in rows 5, 6, and 8, all of which have $a$ as True. This means that we should look for: $x$ = $a$ ∧ something Whatever that "something" is, it should return True for all combinations of $b$ and $c$ except for $b$ True and $c$ False (which was row 7, where $x$ is False).


-2

Hint: How did I come up with this? Well, if $a$ is false, then any conjunction with $a\land(\text{something here})$ will be false as well. That takes care of the top half of the truth table. All that is left, then, is to figure out how to manipulate a combination of $b$ and $c$ to combine with $a$ to give the desired truth values. Thus, what you want is ...


0

Source 1 : http://plus.maths.org/content/os/issue36/features/nishiyama/index. I understand this argument, but it does not feel intuitive. We are given that $\color{green}{P \Longrightarrow Q}$. $\boxed{\text{Case 1 of 2 : } \color{green}{P \Longrightarrow Q} \text{ true}}$ Substitute the green into the tautology $\color{green}{P} \vee \lnot P$ to ...


1

$\forall A\in F$ there is a set of formulas $\Sigma_A \space s.t \space Ass(\Sigma_A)=A$ (because A is definable). Now, lets define $\Sigma= \cup_{A\in F} \Sigma_A$. Prove that : $Ass(\Sigma)=\cap_{A\in F} A$


1

Hint: $K=\mathit{Ass}$ is definable, so all you need to do is find some non-definable set of assignments. You need to involve infinitely many propositional variable, because every truth functional of finitely many variables can be defined by a single formula. How about the set of all possible assignments except the one that makes every propositional ...



Top 50 recent answers are included