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.

learn more… | top users | synonyms (1)

2
votes
2answers
39 views

Hilbert-style proof of $\Gamma\vdash\psi$ and $\Gamma\vdash\chi$ implies $\Gamma\vdash\psi\wedge\chi$

I am given the following Hilbert-style system (for intuitionistic propositional logic): Axiom schemes: $\phi\vee\phi\rightarrow\phi$ $\phi\rightarrow\phi\wedge\phi$ $\phi\rightarrow\phi\vee\psi$ ...
1
vote
1answer
44 views

First order logic,Step in Derivation of Non standard real numbers

This is from first order logic, specifically a section detailing the construction of the non standard real numbers, after Los' theorem And we have that:\ \ Let $L = \{+, ×, <, 0, 1\}$ be the ...
0
votes
1answer
22 views

Converting from DNF to CNF

How to convert a formula from DNF to CNF. Example: $(A \wedge \neg B) \vee (B \wedge \neg A)$ or similar trivial DNFs? It thought it could be work with the distributive law. But I don't know how to ...
3
votes
2answers
45 views

Derivation of $p \supset (\thicksim p \supset q)$ in Gödel's Proof by Nagel/Newman

The actual question I am currently reading Gödel's Proof by Nagel and Newman. Chapter V deals with the formalization and consistency of a simple system of formal logic. On page 50, after giving the ...
0
votes
1answer
50 views

Proof writing involving propositional logic: (p∧ (¬q) ) ↔ ((¬p) ∧ q) ≡ p ↔ q

Prove by using propositional logic: (p∧ (¬q) ) ↔ ((¬p) ∧ q) ≡ p ↔ q Is this possible? I tried solving but i get stuck. LS: = (p∧ (¬q) ) ↔ ((¬p) ∧ q) = ((p∧ (¬q) ) → ((¬p) ∧ q) ) ∧ ( ((¬p) ∧ ...
1
vote
4answers
63 views

Propositional logic - Natural deduction

I'm stuck with a big proof in my homework. I have to use natural deduction to prove something, and I think if I can prove this somehow then I can finish the full proof. Can anyone help? P v Q, ¬P : Q ...
0
votes
2answers
46 views

How to test CNF for satisfiability?

If we have a conjunctive linked expression where only the following clauses are allowed: $A_i, \quad \neg A_i, \quad A_i \vee \neg A_j, \quad \neg A_i \vee A_j$ Example: $A_1 \wedge (A_2 \vee \neg ...
0
votes
1answer
22 views

Propositional logic involving negation and if-statement: precedence

Quick help: So this is confusing me for some reason. I don't know what rule am i missing. I feel both should equal the same no matter how you start it. -(p → q) = (-p → -q) = (p ∨ -q) or -(p ...
2
votes
2answers
94 views

Is set of { AND , EXOR } gates functionally complete set?

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function? XOR gates, NOT gates $2$ to $1$ multiplexers AND gates, XOR gates Three-input gates that ...
0
votes
3answers
59 views

A course on Logic.

I'm looking for a selection of books, in order to properly learn logic, starting from the most basic principles of propositional calculus and going up the ladder, up to higher order logic. My number ...
1
vote
2answers
68 views

If A→(B∧C), Prove (D→A) → (D→C) without using conditional proof

The conditional proof version of this is pretty easy. However, solving this without conditional proof seems to be quite difficult. I tried to turn the premise into: ~A v (B∧C) (~AvB) ∧ (~AvC) I ...
0
votes
1answer
14 views

Translate Quantified FOL Statement into English

I am busy having a war with Tarski's world but I'm obviously not winning right now. I have the following sentence ∀x ∀y ∀z [(Cube(x) ∧ Cube(y) ∧ Cube(z)) → (x=y ∨ x=z ∨ y=z)] On my world I have ...
3
votes
1answer
41 views

If $\models \phi \supset \psi$, then there is a propositional variable variable $p$ that occurs in both $\phi$ and $\psi$.

Full question: Suppose that $\models \phi \supset \psi$, and that $\phi$ is not a contradiction nor $\psi$ a tautology. Show that there is a propositional variable variable $p$ that occurs in both ...
1
vote
2answers
26 views

Proof writing involving propositional logic: (x ∨ y) ≡ ( x ∧ y ) → x ≡ y

Prove by using propositional logic: (x ∨ y) ≡ ( x ∧ y ) → x ≡ y I'm a bit lost here proving by propositional logic that the statement is valid. I don't know how to start this problem. Any help? I ...
1
vote
1answer
29 views

Logical resolution - Why only one pair of complementary literals can be used?

The resources I've come across mention that When the two clauses contain more than one pair of complementary literals, the resolution rule can be applied (independently) for each such pair; ...
0
votes
1answer
26 views

how to simplify and find equivalent of these equivalence formulas?

My question is about propositional logic. Firstly: How can i simplify the formula (F≡¬F) . In my opinion this is simply false ⊥), but i'm not sure about it. Secondly : For the formula (p≡q) , ...
0
votes
0answers
48 views

Given (p∨r),(¬q∨r), use the Fitch system to prove (p → q) → r

I am trying, given (p∨r),(¬q∨r) to use the Fitch System in order to prove (p → q) → r). Any ideas on how I should proceed?
1
vote
1answer
50 views

Hypothesis in Propositional Calculus

So using the collection of statements; "I have tested my app. If I tested my app and it failed the test, I will not try to sell it to customers. If the test was correct then my app failed the test." ...
0
votes
1answer
31 views

Formally prove that the following two premises are contradictory

I have a Proof and Logic paper coming up in a few days and I'm systematically working through papers. I have been using a software called Fitch and mostly constructing formal proofs using Proof by ...
3
votes
1answer
57 views

How can I prove that if $W \cup \{p\}\vdash q$ then $W \vdash p\to q$? [closed]

I saw this yesterday but I can't prove it! Could you please help we with it? I tried some rules but it became so complicated! thank you. If $p$ can be deduced from a set $W \cup \{q\}$, then $p ...
1
vote
1answer
11 views

Exercise IV.4.6. (c) Logic for Mathematicians by Rosser $\vdash P_m \supset P_1\vee P_2\vee \cdots \vee P_n$ if $1 \leq m \leq n$.

The instructions state "using only results of Sec. 4 or earlier portions of the present exercise, prove:" We have shown already the following: (a) $\vdash P\vee Q \supset Q \vee P$ and (b) $\vdash P ...
0
votes
1answer
35 views

Propositional Logic: Entailment

I'm trying to understand propositional logics and the concepts of entailment, but I'm struggling. The concepts don't seem to be difficult in theory, but are very strange-looking when examined. For ...
2
votes
3answers
59 views

Fill out this derivation..

I'm having immense trouble trying to fill out the blanks in this proof. $\newcommand{\tofrom}{\leftrightarrow} \boxed{\begin{array}{l|l:l} 1. & (A\tofrom \neg B) & \text{Premise} \\ 2. ...
1
vote
0answers
95 views

Propositional mathematics [closed]

Consider these lines of code from a C program: if (!(x!=0 && y/x < 1)|| x==0) printf (“True”); else printf (“False”); a. Express the code in this ...
0
votes
1answer
28 views

logical proposition

I have a question about the following proposition as argument, I need to get to an argument that has no number, from 1-2-3 premises. derived: $$ \begin{align} &(P \vee Q)\vee M \\ & R\supset S ...
1
vote
1answer
42 views

How to convert a tautology to Conjunctive Normal Form?

The formula $\varphi \rightarrow ((\psi \rightarrow \sigma) \rightarrow ((\varphi \rightarrow\psi )\rightarrow(\varphi\rightarrow\sigma)))$ is a tautology. I learned the method to find all rows with ...
2
votes
2answers
49 views

Exercise 1.2.10 from Model Theory by Chang and Keisler.

I am reading Model Theory by Chang and Keisler, and I am having some trouble with exercise 1.2.10, which asks me to prove that if $\Sigma \vdash \varphi$ for all $\varphi \in \Gamma$ and $\Sigma \cup ...
1
vote
2answers
60 views

Definition of identity law in the laws of proposition

I'm sure this is an easy one but I'm struggling. From my notes, there's this example on how to simplify a proposition using proposition laws: p $\lor$ (p$\land$ q) $\equiv$ (p $\land$ t) $\lor$ ...
1
vote
0answers
41 views

Satisfiability and validity algorithms?

Any tips for how to go about this? "Assume you have an algorithm A available, that when input with a propositional formula F, shows whether F is satisfiable or unsatisfiable. Construct an ...
1
vote
1answer
62 views

Using general laws, prove that $\lnot(P\leftrightarrow Q)=P\leftrightarrow \lnot Q$

Prove that $\lnot(P\leftrightarrow Q)=P\leftrightarrow \lnot Q$, using general laws I know it can be done by truth tables, but here the question is asked to be answered with general laws like (De ...
0
votes
1answer
89 views

How to apply the resolution rule to $\{q;\neg q\}\{q;\neg q\}$?

How would one apply the resolution rule to $\{q;\neg q\}\{q;\neg q\}$? Would one obtain $\{q;\neg q\}$? $\{q;\neg q\}$? something else? I thought it would result in the empty set, yet it seems ...
2
votes
0answers
26 views

n-formula for k n-evaluations

I am trying to solve the following problem Let $N = \{0, 1, 2, ...\} $ is the set of natural numbers. Propositional variables are $ A_{n}$ for $n \in N $ . An evaluation $v$ is called ...
3
votes
1answer
55 views

Is an empty conjunction in propositional logic true?

Consider an illustratory formula $\psi \equiv \bigwedge_{i \in \emptyset} false$, does $\psi$ valuate to $true$? Is such a formula ill-formed? If not, is there a symbol for an empty formula? The ...
4
votes
3answers
210 views

Vacuous Truth and Universal Conditional Statements

Sometime after I began studying conditional statements, I started having difficulty understanding vacuous truth. For instance, the fact that for any set $A$ we have $\emptyset\subset A$ is commonly ...
1
vote
2answers
49 views

Proof for ∨ distributing over →

I'm am stuggling to prove the following: x ∨ ( y → z ) ≡ ( x ∨ y ) → ( x ∨ z ) After making a truth table, I know that disjunction distributes over implication but I am failing to prove the above ...
4
votes
2answers
83 views

Creating a new connective in Propositional Logic

In the exercise below, is included a new connective ($\sqsubset$), and I'm stuck in how to deal with it. We can view the relation $\vDash$ $\varphi$ → $\psi$ as a kind of ordering. Put $\varphi$ ...
2
votes
0answers
71 views

Implication, conjunction and disjunction distributivity problems

I have proven using theorems that implication is left distributive over conjunction: x → (y ∧ z) ≡ ( x → y ) ∧ ( x → z ) Proof: x → (y ∧ z) = ¬x ∨ ( y ∧ z ) = ( ¬x ∨ y ) ∧ ( ¬x ∨ z ) = ( x → ...
0
votes
4answers
60 views

Prove that B is logically equivalent to C if and only if B logically implies C and C logically implies B.

It's exercise 1.8 in Introduction to Mathematical Logic, Sixth Edition by Elliot Mendelson. I couldn't prove it with the definitions given by the author. How should I approach the problem? A is said ...
1
vote
2answers
50 views

Propositional Logic - Formal Proofs using natural deduction

I have a question I have come across in an old exam paper which I am trying to work through. It states that a formal proof must be given using the rules of natural deduction Now generally what I ...
0
votes
1answer
17 views

Another Translation to Propositional Logic Trouble

I've just stumbled upon this rather seemingly simple problem: Translate this sentence into propositional logic: You can go to the fair if you are not sick, but otherwise you must stay home and ...
0
votes
1answer
28 views

How to prove logical equivalency of two propositions that have quantifiers?

I came across this question and I'm not sure if I fully understand how to do it. The question asks to show that ∀x(P(x) → q) is logically equivalent to ∃xP(x) → q. The way that I was taught to do ...
1
vote
3answers
41 views

Not understanding how to do this logic question

Let $A, B$ be propositional formulas. Demonstrate that if there exists a propositional formula $C$ such that $A$ is a logical consequence of $C$ and $B$ is a logical consequence of $\neg C$, then ...
1
vote
3answers
44 views

Proving equivalence of $(P \vee Q \vee R)$

I'm trying to prove the below equivalence without truth table. $(P \vee Q \vee R)$ and $(P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (R \wedge \neg P) \vee (P \wedge Q \wedge R)$ I begin with the ...
0
votes
1answer
18 views

rule of inference proof

"Either i go to library or if i wait for my mom then i have to go to the party." "I will go to the party if i meet my friends" "if i go to the library then i will finish my homework." "I did not ...
1
vote
1answer
34 views

How to distribute this logic expressions

I want to prove the binary resolution proof that if I have $a \vee b$ and $ \lnot b \vee c$ then this will imply $$ a \vee c$$ Now I want to do it this way $$(a \vee b) \wedge ( \lnot b \vee c) ...
0
votes
1answer
15 views

Big notation Propositional Formulas

I am reading a lecture and there is a sentece that say: Every tautology $\tau$ on $n$ variables has an proof in which there are at most $2^{O(n)}$ formulas. I know that $O$ is the big notation ...
0
votes
2answers
33 views

Indirect proof of universal statement [closed]

Can I prove $\neg R(x) \implies \neg R(y)$ by proving $\neg \neg R(y) \implies \neg \neg R(x)$? Can I also prove that by proving $R(y) \implies R(x)$?
1
vote
0answers
41 views

how to determine if formula satisfies without creating a truth table

$(p \wedge q \wedge r) \wedge (\neg p \vee r)$ So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p ...
2
votes
1answer
39 views

Formalising a structure and determining functional completeness

Background Suppose we have switches and [boxes with light bulb]. We can put both switches or boxes inside a box. Depending on the type of box it is, we need a certain number of switches or boxes ...
1
vote
1answer
29 views

Help with a use of the Propositional Compactness Theorem

I'm trying to show that if a set of sentences $\Sigma$ is such that for every valuation $v:A \rightarrow 2$, there is some $p\in\Sigma$ with $v^*(p)=1$, then there is are $p_1,\ldots,p_n\in\Sigma$ ...