# Tagged Questions

Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

48 views

### tautologies and truth values

I have no idea how to start. really appreciate some help here. Let P and Q be propositions. A statement S (involving P , Q ) is called a tautology iff for any truth-values of P and Q , the statement ...
58 views

### Does the => truth table break mathematical induction?

Since $F \Rightarrow F$ and $F \Rightarrow T$ both evaluate to $T$ with the truth table for $\Rightarrow$, does this not break mathematical induction? For example, once you show the base case holds ...
43 views

### What's next step to prove this boolean expression?

I need to prove that the first member of this equivalence is true: $$(p\vee q)\wedge (\sim p \wedge (\sim p\wedge q))\equiv \sim p \wedge q$$ I have reached the following point, but I don't know how ...
76 views

### Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation

I'm supposed to prove the validity of the following $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
112 views

### Difference between a proposition and an assertion

It may be a silly doubt, but let me ask this. What is the difference between a proposition and an assertion? I know there's a very thin line between the two terminologies, but I'm unable to get ...
46 views

### If $\models \neg \phi$, then $\models \phi^\circ$, where $\phi^\circ$ is the “semi-dual” of $\phi$

This is exercise 1.3.22 from Hinman's Fundamentals of Mathematical Logic. Let $\mathrm{Sent}_{\neg, \vee, \wedge}$ be the set of all sentences from propositional logic closed under negation, ...
53 views

42 views

### Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$

Show that $(A\Delta B) \cup C = (A\cup C) \Delta (B\setminus C)$ I want to show it algebraically, but I just can't make it work.
69 views

### Are the logical [equivalence] laws sound and adequate without de Morgan's law?

I need to say whether the system of logical laws made of: Double negation Commutative Associative Distributive Idempotent Implication Contradiction de Morgans Absorption Equivalence is sound and ...
88 views

### Questions about Gödel, formal systems, propositional calculus and first order logic.

I've been reading Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid, and I'm loving it, though there are some things I don't quite understand yet. Propositional Calculus is a formal system, ...
35 views

### prove [(¬M∧R)∧Q |- Q∨T [closed]

prove [(¬M∧R→Q |- Q∨T really confused :(
53 views

### Solve the following proof : M |- M ∨ {[(Z∨S) ∧ (¬] → (C↔D)}

Solve the following proof : M |- M ∨ {[(Z∨SC↔D)} I try to proof above question with the following (F⋀Z)⋀ → (C↔D) 1 (F⋀Z)→C 2 F⋀Z 1⋀E 3 F 2⋀E really confused :( this ...
45 views

### Analyzing logical form of the statements

I have four statements given as exercises in the book: How to prove it. Sa : Alice and Bob are not both in the room. Sb : Alice and Bob are both not in the room. Sc : Either Alice or Bob is not ...
29 views

### Propositional Logic - Conditional Proof

I'm confused doing one problem. The problem is to show that $$(P\vee Q \implies R) \implies (P\wedge Q \implies R)$$ using Rule C.P. What I have done so far: Assumed antecedent of the conclusion as ...
115 views

### Law of Clavius explained

Law of Clavius states $\sim P \Rightarrow P \vdash P$ And the only explanation I sort of understand is ...
50 views

### Universal 2-bit gates

I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus ...
71 views

### Omitting parantheses in formulas

Lately I read the following: parentheses can always be omitted, so instead of $((\neg A)\Rightarrow B)$ we may write $(\neg A)\Rightarrow B$. But we may not write $\neg A\Rightarrow B$, because ...
35 views

### Solving Boolean expression

(A+C+D)(A+C+D’)(A+C’+D)(A+B’) This is my first attempt on solving four algebraic terms using boolean expression. I am stuck,please help me. I have a test tommorow. Thanks!
90 views

### Why do we need truth functional completeness?

This might sound a little too basic, perhaps too basic for most people to talk about. The question seems vaguely structured - I'm not sure how to phrase it better. Question: Why do we need truth ...
97 views

### Is it necessary for a statement to have an inverse in propositional logic?

I know that it may be rather self-evident that every statement must possess an inverse, however, is there a way to prove this in propositional calculus or is it considered an axiom? (Note: By the ...
219 views

75 views

### How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
270 views

### How to prove a logical implication?

Question: Using the Laws of Logic and Rules of Inference, prove that $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$ I just don't know how to apply the Rules of ...
24 views

### Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
42 views

61 views

### How Do You Show That There Exist Infinitely Many Organic Tautologies?

This question takes inspiration from this question. A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula ...
55 views

### Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
82 views

### Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
73 views

### Prove $(p \rightarrow q) \land (r \rightarrow s) \implies ( \neg p \lor \neg r \lor q \lor s)$

$$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ I have some problem with formula: $$(p \rightarrow q) \land (r \rightarrow s)$$ \equiv(\neg p \lor q) ...
43 views

33 views

### Does a Length Always Exist such that a Tautology Always Exists Beyond That Length?

Suppose we have some set of fixed connectives such that tautologies exist and we write everything in Polish notation. The length of a WFF consists of the number of symbols that it has. WFFs can get ...
### Finding a morphism from one boolean expression to another i.e. $\phi :(x \Rightarrow y) \rightarrow (y \vee z)$
What I would like to do is figure out how to get from $(x \Rightarrow y)$ to $(y \vee z)$, that what I could AND or OR to $(x \Rightarrow y)$ so as to give $(y \vee z)$. Breaking this down I ...
### Constructing a tautology given a set $\Sigma \subset$Prop(A) with special properties.
I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The ...