Sound and complete, Computer Engineering

Assignment Help:

Dictator Dim wants to replace counting, in particular, counting the population of his land. To keep an accurate population count, Dictator Dim has instructed his secretary to add one + symbol to a record each time a citizen is born, and one - symbol to the record whenever a citizen dies. This has been going on ever since his rule began.

Dictator Dim is not concerned so much with the actual total population of his lands, just with the net change in population since his rule began. He would be forever disgraced if the net population change were ever negative. Refusing to solve this problem by counting, Dictator Dim instructs his secretary to find a sound and complete logic for the subset of all records that would not disgrace him.
More formally, define the following truth concept WFF's = {+; -}, i.e., all strings composed of only plus and minus symbols.
A WFF x is true if every prefix of x contains at least as many + symbols as - symbols.

Find a logic for this truth concept by proving that it is sound and complete. Hint: it may help to define additional judgement form(s)


Related Discussions:- Sound and complete

What is small computer systems interface, Q. What is Small Computer Systems...

Q. What is Small Computer Systems Interface? The other well-liked way is to connect a disk drive to a PC by a SCSI interface. Common drive choice for high-end workstations or s

What is a priority interrupt, What is a Priority Interrupt? A priority ...

What is a Priority Interrupt? A priority interrupt is an interrupt that establishes a priority over the various sources to determine which condition is to be serviced first whe

What are the end-to-end layers of osi structure, What are the end-to-end la...

What are the end-to-end layers of OSI structure The layers 4-7 of ISO-OSI reference model communicate with peer entities in end systems. There is not any communication with ent

Determine the example - fork-join, Determine the Example - "fork-join" ...

Determine the Example - "fork-join" module initial_fork_join(); reg clk,reset,enable,data; initial begin $monitor("‰g clk=‰b reset=‰b enable=‰b data=‰b", $time, cl

State the benefits of encapsulation, State The Benefits of Encapsulation ...

State The Benefits of Encapsulation To hide the details of a class, you can declare that data or implementation in the private part of class so that other class clients will n

What is access latency and rotation speed, Q. What is Access latency and Ro...

Q. What is Access latency and Rotation Speed? Access latency: A disk access basically moves the arm to selected cylinder and waits for rotational latency that may take less t

What is an i/o buffer, What is an I/O buffer? I/O buffer: One ty...

What is an I/O buffer? I/O buffer: One type of input-output requirement arises from devices which have a very high character density as disks and tapes. With these chara

Show division and multiplication operation, Q. Show Division and multiplica...

Q. Show Division and multiplication operation? These operations can be represented as x + y = (N x   × 2 Ex-Ey + N y ) × 2 Ey and x-y = (N x × 2 Ex-Ey -N y ) × 2 Ey

State the use of erasable programmable read only memory, Erasable programma...

Erasable programmable read only memory (EPROM) This is a special type of PROM which can be erased by exposing it to ultraviolet (UV) light. Once it has been erased, it can be r

Illustrate about system memory-management mode, Memory - management mode ...

Memory - management mode System memory-management mode (SMM) is on the same level as protected mode, real mode and virtual mode though it is provided to function as a manager

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd