Tag Info

New answers tagged

1

Hint 1: The proofs mainly rely on two basic rules of inference. Conjunction-Elimination ($\wedge{-}$ , $\wedge \rm E$, or similar abreviation ): $\quad A\wedge B \vdash A$ and Disjunction-Introduction ($\vee{+}$, $\vee \rm I$, et cetera): $\quad A\vdash A\vee B$ Plus: Modus Ponens ($\rm MP, \to E$). $\quad A, A\to B\vdash B$ and Modus Tollens ($MT, ...


0

What do you mean by "solve"? If to "solve" something of the form $A \vdash B$ means "produce a proof in the formal proof system in My Logic Text from premiss $A$ to $B$" (which is the natural reading) then we need to know which text you are using! In this case you have $M \vdash M \lor X$. And it doesn't matter what $X$ is, for in any standard logical ...


0

The truth table of a 2-bit gate will have two input columns and two output columns: Input | Output A B | X Y -------+-------- 0 0 | ? ? 0 1 | ? ? 1 0 | ? ? 1 1 | ? ? In order for the gate to be reversible, each output column must contain exactly two ones and two zeroes. This limits the possible output columns to one of ...


1

I also think Sa should be $$\neg (A \land B), $$ or . which includes the event your translation missed that neither Alice nor Bob is in the room.


2

I'm assuming the exercise here asked you to translate the sentences into propositional calculus. Sa should be translated as $\neg (A \wedge B)$; it would have been $A \oplus B$ if it had said "Either Alice or Bob are in the room, but not both". For Sb, the more literal translation would be $\neg A \wedge \neg B$, but in classical logic what you wrote is ...


1

" ∼P⇒P⊢P" You can read this as meaning "Suppose that the negation of a proposition implies that proposition. It follows that the proposition is provable." Or equivalently in Polish notation: CNpp $\vdash$ p. No one less than Aristotle himself did not understand the law of Clavius. With the principle of bivalence in mind, the only way that the negation ...


2

''Clavius' law'' is just a variant of proof by contradiction or reductio ad absurdum: If $\sim\! P$ implies $P$, then $\sim\! P$ is inconsistent (because it then also implies the contradiction $\sim\! P\land P$). Therefore $P$. Formally: $\sim\! P \Rightarrow P\vdash P$. You should be able to formulate any proof by contradiction as an instance of ...


1

Some more examples are $$\sqrt{8}×\sqrt2=\sqrt{16} =4$$ $$\sqrt2×\sqrt{32}=\sqrt{64} =8$$ $$\sqrt5×\sqrt5=\sqrt{25} =5$$ In this way product of two irrational number is rational.


2

As others have mentioned, the main issue here (one that used to bother me as well) concerns operator precedence. As Henning notes, a convention has to be established first for anything to make sense and to avoid ambiguity. Broadly speaking, the following is a little table that lists binary connectives and their corresponding ranks: \begin{array}{ccc} \hline ...


2

It ought to be clear that it's unworkable to allow omitting the parentheses in both $(\neg A)\Rightarrow B$ and $\neg(A\Rightarrow B)$. These are two different formulas with different meanings, yet each of them becomes "$\neg A\Rightarrow B$" if we omit the parentheses. Thus, in order to be sure what we're speaking about we need either to declare that ...


3

All of this is a matter of order of operations (or operator precedence). For instance, this is carefully defined in any programming language. From the same wikipedia article: In logic, $\neg$ has higher precedence than $\wedge$, $\wedge$ higher than $\vee$, and $\vee$ higher than $\rightarrow$.


1

I assume that '+' is for '$\vee$' Look at first two terms, and let $A+C=T$: $$ (A+C+D)(A+C+D') = (T+D)(T+D') = TT+DT+TD'+DD' = T(T+D+D')+DD' = T(T+1)+DD' = T = A + C. $$ Ok, let's simplify $(A+C)(A+C' + D)$: $$ (A+C)(A+C' + D) = (C+A)(C' + (A + D)) = CC' + AC' + C(A+D) + A(A+D) = AC' + C(A+D) + A = (A + AC') + C(A+D) = A + CA + CD = A + CD. $$ And last ...


1

Hint: Simplify bracket by bracket. For example $$(A+C+D)(A+C+D') = AA+AC+AD'+CA+CC+CD'+DA+DC+DD' \\ = A+AC+AD'+CA+C+CD'+DA+DC \\= A+AC+AD'+C+CD'+DA+DC \\= A+AC+C+A(D+D')+C(D+D') \\= A+AC+C+A+C=A+C+AC=A+C$$ Now you can put this expression in the place of the first two brackets and solve again, keeping the rules of simplifying in mind.


2

Your reasoning seems correct. However, I would add that if a set of connectives qualifies as truth-functional complete, that tells us that all functions with the same input and output sets can get computed. A truth-functionally incomplete set of connectives has some functions on the set of truth values which can't get computed. This isn't just about ...


2

There's a related question, which I suspect might be part of what the OP intends to ask: Is "logic without negation" a thing? The answer is yes, in a variety of ways: In intuitionistic logics, we do have the symbol "$\neg$"; however, it does not behave the way we might expect negation to behave. For example, "$\varphi \vee \neg\varphi$" is usually ...


1

In general science, there's a distinction between definitions and axioms that I think is important to recognize. A definition arbitrarily associates a linguistic symbol with an algorithm. Examples include "Let X = 5", "Let Red be 400-484 THz," "Let +(x,y) be the addition algorithm," &c. An axiom is a type of proposition utilizing definitions that is ...


1

More formal proofs exist, but basically: Every atomic predicate always has a negation.   If $p$ is such a predicate, $\neg p$ is the negation. Every logical connective will have a dual; thus every compound predicate has a negation through deMorgan style rules of dual negation.   If $\circ, \bullet$ are such duals, and $p, q$ are predicates, then ...


2

The fact that you can form a negation of every formula is simply a property of the logical language. It will be formally stated as part of the definition of "well-formed formula": Whenever $\varphi$ is a formula, $¬(\varphi)$ is a formula too. You could consider that an "axiom" (the distinction between axioms and definitions being somewhat fluid) if you ...


0

Yes: given a quantified wff F, there is an algorithm to negate F: you start with the outermost quantifier, negate it, and do so until you are done with the quantifiers. Negation at each point preserves well-formedness. Negations are done like this: 1)~$(\forall x P_{xyz..})$ is $\exists x $ ~P 2)~$(\exists x P_{xyz..})$ is $\forall x$ ~$P_{xyz..}$ And ...


3

As per my answer to your previous post , I'll assume that we have available the Deduction Th, that is provable (together with $\vdash A ⇒ A$) from A1) and A2) only. For : $[¬A⇒(¬B⇒C)] \Leftrightarrow [¬(¬A⇒B)⇒C]$, we need some preliminary Lemma : Lemma 1 : $A ⇒ B, B ⇒ C \vdash A ⇒ C$ --- Syllogism "derived rule" : easily provable with DT Lemma 2 ...


1

For : $[(A⇒¬B)⇒(A⇒C)]⇒[A⇒(¬B⇒C)]$ we assume that we have available the Deduction Th, that is provable (together with $A ⇒ A$) from A1) and A2) only. 1) $[(A⇒¬B)⇒(A⇒C)]$ --- assumed [a] 2) $A$ --- assumed [b] 3) $¬B$ --- assumed [c] 4) $¬B⇒(A⇒¬B)$ --- axiom A1) 5) $A⇒¬B$ --- from 3) and 4) by Modus Ponens 6) $A⇒C$ --- from 1) and 5) by Modus ...


1

Xor is the same as addition modulo 2. Addition you can take in any order.


2

Hints: Denoting XOR by $\Delta$, it would be enough to prove $(a\Delta b)\Delta c=a\Delta(b\Delta c)$, then apply this several times. $a_1\Delta a_2\Delta a_3\Delta\dots\Delta a_n\ $ is true iff exactly an odd number of $a_i$'s are true.


-2

I have had to flesh out the logic of this myself. (after a late night of studying necessary and sufficient conditions for LSAT purposes, no less. I was a philosophy major and I couldn't just let it be a surface understanding). First, to all you legitimate technicians on this forum (whether by credential or study) if I have made some errors here please ...


2

Let $v_1,\ldots,v_n$ be the variables and $\phi(v_1,\ldots,v_n)$ an expression in these using only $\land$ and $\lor$ as connectives. Then we can rewrite this as $$\phi(v_1,\ldots,v_n)\iff v_n\land\phi_1(v_1,\ldots,v_{n-1})\lor \phi_2(v_1,\ldots,v_{n-1})$$ so that we can represent an expression in $n$ variables as a pair of expressions in $n-1$ variables. ...


4

You are really asking how many different boolean functions of $n$ variables can be constructed using $\land$ and $\lor$. Assuming you don't allow empty expressions (always true or always false), this is OEIS sequence A007153.


0

First note that $$ (\neg p \lor q)\equiv p\rightarrow q $$ So now we have $$(\neg(\neg p \lor q) \lor r) \rightarrow (\neg p \lor (\neg q \lor r))$$ $$\equiv (\neg(p \rightarrow q) \lor r) \rightarrow (\neg p \lor (q \rightarrow r))$$ $$\equiv ((p \rightarrow q) \rightarrow r) \rightarrow ( p \rightarrow (q \rightarrow r))$$ $$\equiv \mbox{tautology} $$


0

In the referenced List of rules of inferfence, you have the rule for Conditional Introduction (or Conditional proof), that is fundamental to prove a formula with a conditional : 1) $¬(¬p∨q)∨r$ --- premise 2) $(¬p∨q) \to r$ --- from 1) by Material implication : $(\lnot \varphi \lor \psi) \Leftrightarrow (\varphi \to \psi)$ [with : $\lnot p \lor q$ as ...


1

You should start supposing the contrary of the conclusion, that is, $$\neg(\neg p \vee (\neg q\vee r)))$$ Now, apply twice the De Morgan's law for $\neg(X\vee Y)$: $$p\wedge q \wedge\neg r$$ Eliminate $\wedge$ to obtain $\neg r$. Now, use the premise and eliminate $\vee$: $$\neg(\neg p\vee q)$$ Apply again De Morgan's law: $$p\wedge \neg q$$ Now, eleminate ...


0

[~p^(pvq)]->q [pv(~p^~q)]vq [(pv~p)^(pv~q)]vq [T^(pv~q)]vq (pv~q)vq pvT T ====================== Therefore its a tautology^^


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 ...



Top 50 recent answers are included